Kombinatoryka

Teoria

Wybieranie \(k\)-elementowych podzbiorów ze zbioru \(n\)-elementowego możemy rozdzielić na 4 przypadki. Permutacje możemy potraktować jako szczególny przypadek, kiedy \(k = n\).

Nazwa Czy elementy w zbiorze się powtarzają? Czy kolejność elementów w podzbiorach jest istotna? Liczba możliwych zestawień
Permutacje nie tak \(P_n = n!\)
Wariacje z powtórzeniami tak tak \(W^k_n = n^k\)
Wariacje bez powtórzeń nie tak \(V^k_n = \frac{n!}{(n-k)!}\)
Kombinacje nie nie \(C^k_n = \binom{n}{k} = \frac{n!}{(n-k)!k!}\)

Symbol \(\binom{n}{k}\) czytamy „n po k” i jest to tzw. symbol Newtona. Poniżej znajdują się jego podstawowe własności.
$$
\begin{array}{cc}
\binom{0}{0} = 1 & \binom{n}{0} = 1 \\
\binom{n}{n} = 1 & \binom{n}{1} = n
\end{array}
$$

Przykłady

Poniższa tabela przedstawia 4 przypadki dla zbioru 3-elementowego. W każdym przypadku liczba możliwych zestawień jest inna. W permutacji nie wydzielamy podzbiorów – do policzenia liczby możliwych podzbiorów wykorzystujemy wszystkie elementy. Wariancja z powtórzeniami daje najwięcej podzbiorów, a kombinacja najmniej.

Zbiór Zadanie Liczba rozwiązań Możliwe podzbiory
Z = {a, b, c} Permutacje \(P_3 = 3! = 6\) {abc, acb, bac, bca, cab, cba}
Wariacje z powtórzeniami (k = 2) \(W^2_3 = 3^2 = 9\) {ab, ba,ac, ca, bc, cb, aa, bb, cc}
Wariacje bez powtórzeń (k = 2) \(V^2_3 = \frac{3!}{(3-2)!} = 6 \) {ab, ba, ac, ca, bc, cb}
Kombinacje (k = 2) \(C^2_3 = \binom{3}{2} = \frac{3!}{(3-2)!2!} = 3\) {ab, ac, bc}

Łatwo zauważyć, że kombinacje w przeciwieństwie do wariacji, nie mają ustalonej kolejności elementów. Dwie różne wariacje, różniące się tylko kolejnością elementów, dają tę samą kombinację. Liczba \(k\)-elementowych kombinacji jest więc mniejsza od liczby \(k\)-elementowych wariacji tylokrotnie, ile jest różnych permutacji takiego ciągu. Zależność tą opisuje poniższy wzór.
$$
C^k_n = \frac{V^k_n}{P_n} = \frac{n!}{(n-k)k!}
$$