Kombinatoryka — permutacje, wariacje i kombinacje

Zawsze zaczynaj od dwóch pytań: (1) czy kolejność ma znaczenie? (2) czy element może się powtórzyć?

$$P$$_n=n! \qquad V_n^k=\frac{n!}{(n-k)!} \qquad W_n^k=n^k \qquad C_n^k=\frac{n!}{k!(n-k)!}

Warunki: $n,k\in\mathbb{N}$; dla $V$_n^k i $C$_n^k dodatkowo $0\le k\le n$. W $W$_n^k=n^k (wariacja z powtórzeniami) liczba miejsc $k$ nie musi być $\le n$.

Dwie reguły zliczania. Reguła mnożenia: gdy wybór składa się z kolejnych etapów, liczby możliwości mnożymy ($m\cdot n$; np. $5\cdot 4\cdot 3$). Reguła dodawania: gdy rozbijasz zadanie na rozłączne przypadki, liczby dodajesz ($m+n$) — ale tylko gdy przypadki się nie pokrywają (przy nakładaniu: $|A\cup B|=|A|+|B|-|A\cap B|$).

Permutacje z powtórzeniami (gdy część elementów jest identyczna): $P$_n^{(n₁,\dots,n_r)}=\dfrac{n!}{n₁!\,n₂!\cdots n_r!}, przy $n$₁+\dots+n_r=n — np. liczba anagramów słowa MAMA (dwa M, dwa A): $\dfrac{4!}{2!\,2!}=6$.

Wizualizacja· Który model zliczania wybrać?

Co zauważyć: Wszystkie n? → permutacje n!. Kolejność bez znaczenia → kombinacje C(n,k). Kolejność ważna: bez powtórzeń → n!/(n−k)!, z powtórzeniami → nᵏ.

Permutacje / wariacje / kombinacje — porównanie:

Jeśli nie pamiętasz wzoru, wróć do sensu: wybierasz czy ustawiasz?