Kombinacje

Kombinacje stosujemy wtedy, gdy z jakiegoś zbioru obiektów wybieramy określoną liczbę obiektów, a kolejność, w jakiej je wybieramy, nie ma znaczenia. Typowym przykładem jest Lotto — w maszynie losującej jest 49 liczb i losuje się z nich 6 liczb, przy czym nie ma znaczenia, w jakiej kolejności zostaną wylosowane.

Wyprowadzenie wzoru

Weźmy jakiś zbiór M, na przykład M = {a, b, c, d, e}. Wtedy k-elementowa kombinacja to podzbiór K ⊆ M, który zawiera dokładnie k elementów. Ponieważ K jest zbiorem, kolejność oczywiście nie ma znaczenia. Trzyelementową kombinacją zbioru M może więc być {a, b, d} albo {b, c, d}.

Różnica w porównaniu z wariacjami polega na tym, że w wariacjach liczyła się kolejność, więc (a, b, e) i (e, b, a) to różne wariacje, ale ta sama kombinacja, bo (a, b, e) i (e, b, a) zawierają te same elementy; to, że są w innej kolejności, w kombinacjach nas nie interesuje.

Możemy jednak wykorzystać wariacje, żeby otrzymać wzór na liczbę wszystkich różnych kombinacji. Wiemy, że k-wyrazowych wariacji zbioru n-elementowego jest dokładnie

$$ V_n^k = \frac{n!}{(n-k)!}. $$

Gdybyśmy więc policzyli liczbę wszystkich trzywyrazowych wariacji poprzedniego zbioru M = {a, b, c, d, e}, otrzymalibyśmy V₅³ = 60 różnych wariacji. Mielibyśmy tam jednak dla każdej trójki również wszystkie jej permutacje. Czyli mielibyśmy tam trójkę abc, ale też trójki acb, bac, bca, cab i cba. To jest sześć różnych wariacji, ale tylko jedna kombinacja, bo wszystkie mają te same elementy.

Jeśli więc mamy jakąś trójkę, to ile istnieje różnych permutacji tej trójki? Dokładnie 3!. Innymi słowy, trzywyrazowych wariacji jest dokładnie 3! razy więcej niż trzyelementowych kombinacji. Zamiast jednej kombinacji liczymy 3! wariacji, po jednej dla każdej permutacji danej trójki. Jeśli więc liczbę wariacji podzielimy przez 3!, otrzymamy liczbę kombinacji.

Poprzednie rozumowanie możemy uogólnić i powiedzieć, że jeśli szukamy liczby wszystkich różnych k-elementowych kombinacji zbioru n-elementowego, to ta liczba, którą oznaczymy C_n^k, jest równa

$$ C_n^k = \frac{V_n^k}{k!}, $$

czyli liczba wariacji podzielona przez k!, co jest liczbą permutacji każdego ciągu k-wyrazowego. Wzór możemy przekształcić, rozpisując wzór na liczbę wariacji:

$$ C_n^k = \frac{V_n^k}{k!} = \frac{n!}{(n-k)!}\cdot\frac{1}{k!} = \frac{n!}{(n-k)!\cdot k!}. $$

Przykład: liczba dwuelementowych kombinacji zbioru {a, b, c} wynosi

$$ C_3^2 = \frac{3!}{1!\cdot2!} = 3 $$

i są to te kombinacje: {a, b}, {a, c} i {b, c}. Dla trzyelementowych kombinacji wyjściowego zbioru M = {a, b, c, d, e} otrzymalibyśmy liczbę

$$ C_5^3 = \frac{5!}{(5-3)!\cdot3!}=10 $$

i są to te kombinacje: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Symbol Newtona

Zapisu wzoru za pomocą C_n^k używa się rzadziej, zamiast niego zwykle używa się tak zwanego symbolu Newtona. Symbol Newtona ma taką postać

$$ {n \choose k} $$

jest to coś w rodzaju ułamka bez kreski ułamkowej (którą i tak z przyzwyczajenia będziesz pisać), ale z nawiasami (te nie są opcjonalne, muszą tam być). Symbol Newtona czytamy „n nad k” (albo „n po k”). Jego wartość jest taka sama jak C_n^k.

$$ {n \choose k} = \frac{n!}{(n-k)!\cdot k!} $$

Jeśli więc mamy zbiór 5-elementowy i wybieramy z niego czwórki, to ich łączna liczba wyniesie

$$ {5 \choose 4} = \frac{5!}{1! \cdot 4!} = 5. $$

Podstawowe zależności

Dla symbolu Newtona i n ∈ ℕ zachodzi:

$$\begin{eqnarray} {n \choose 0} = {n \choose n} = {0 \choose 0} &=& 1\\ {n \choose 1} &=& n \end{eqnarray}$$

Dalej dla n, k ∈ ℕ₀ i k ≤ n zachodzi

$$\begin{eqnarray} {n \choose n - k} &=& {n \choose k}. \end{eqnarray}$$

A dla n, k ∈ ℕ₀ i k < n zachodzi

$$\begin{eqnarray} {n \choose k} + {n \choose k+1} &=& {n+1 \choose k+1}. \end{eqnarray}$$

Rozwiązane przykłady

1. Zacznijmy od wspomnianego już Lotto. Losuje się w nim z maszyny, w której jest 49 kul, łącznie 6 kul. Ile różnych wyników można wylosować?

   Po pierwsze — czy liczy się kolejność losowania liczb? Nie, typujemy tylko liczby, nie ich kolejność. Będziemy więc korzystać z kombinacji. Mamy łącznie 49 kul, losujemy 6 kul, więc otrzymujemy symbol Newtona

   $$ {49 \choose 6} = \frac{49!}{(49-6)!\cdot6!}=\frac{49!}{43!\cdot6!} = 13{,}983,816 $$

   Istnieje więc łącznie 13 983 816 możliwych wyników losowania. Co, nawiasem mówiąc, daje prawdopodobieństwo wygranej przy jednym zakładzie 1/13 983 816, czyli 0,00000715112%.

2. Bartek, znany podrywacz, jest akurat na wiejskiej zabawie, na której jest 13 pięknych dziewczyn, którymi byłby zainteresowany. Bartek wie, że w ciągu wieczoru zdoła oczarować 4 różne dziewczyny. Spośród ilu różnych czwórek może Bartek wybierać?

   To znowu prosty przykład na kombinacje: kolejność nie ma znaczenia, Bartek będzie tak samo czarujący dla pierwszej dziewczyny, jak dla ostatniej. Mamy więc zbiór 13 dziewczyn, z którego wybieramy za każdym razem 4 dziewczyny. Prowadzi to do symbolu Newtona

   $$ {13 \choose 4} = 715. $$

3. Masz grupę pięćdziesięciu osób — połowa to mężczyźni, połowa kobiety. Ile istnieje różnych trójek osób, jeśli nie mogą się one składać z osób tylko jednej płci (czyli w trójce nie mogą być trzej mężczyźni ani trzy kobiety)?

   To już trochę trudniejsza kombinacja. Jeśli wykluczymy trójki jednopłciowe, zostaną nam tylko dwie możliwości składu trójki — dwóch mężczyzn i jedna kobieta albo jeden mężczyzna i dwie kobiety, przy czym liczba kombinacji pierwszego rodzaju (dwóch mężczyzn i jedna kobieta) będzie taka sama jak liczba kombinacji drugiego rodzaju. Wystarczy więc obliczyć liczbę kombinacji pierwszego rodzaju i pomnożyć ją przez dwa. Teraz to już znowu bułka z masłem. Wyznaczamy liczbę różnych par mężczyzn, czyli dwadzieścia pięć nad dwa, i mnożymy ją przez liczbę sposobów wyboru jednej kobiety (to daje dwadzieścia pięć, zobacz podstawowe zależności powyżej, konkretnie drugi wiersz). Ten wynik mnożymy już tylko przez dwa i mamy ostateczny wynik.

   $$ 2 \cdot {25 \choose 2} \cdot {25 \choose 1} = 15000. $$

4. W pudełku jest 15 produktów, z których 4 są wadliwe. Na ile sposobów można wybrać 6 produktów tak,

   • żeby żaden nie był wadliwy? W tej sytuacji wybieramy 6 produktów spośród 15 − 4 = 11 produktów, które nie są wadliwe. Otrzymujemy więc symbol Newtona

     $$ {11 \choose 6} = 462. $$

   • żeby dokładnie jeden produkt był wadliwy? Wybieramy więc zbiór, który zawiera 5 dobrych (niewadliwych) produktów i 1 wadliwy. Dobrych produktów mamy łącznie 11, wadliwych 4. Stosujemy regułę mnożenia i otrzymujemy wynik:

     $$ {11 \choose 5} \cdot {4 \choose 1} = 1848 $$

   • żeby co najwyżej jeden był wadliwy? Do rozwiązania wykorzystamy poprzednie wyniki. Wiemy, że mamy łącznie 462 możliwości wyboru dokładnie 6 dobrych produktów i 1848 możliwości wyboru pięciu dobrych i jednego wadliwego produktu. Stosujemy więc regułę dodawania, sumujemy te wyniki i dostajemy to, czego szukamy, czyli co najwyżej jeden wadliwy produkt (= albo żaden wadliwy, albo dokładnie jeden). Wynik to: 462 + 1848 = 2310.