Kombinacja

Używamy kombinacji, gdy wybieramy określoną liczbę obiektów ze zbioru obiektów, a kolejność, w jakiej wybieramy te obiekty, nie ma znaczenia. Typowym problemem jest Sportka - mamy 49 liczb w puli i losujemy 6 z nich, bez względu na to, w jakiej kolejności je wylosujemy.

Wyprowadzenie wzoru

Rozważmy pewien zbiór M, na przykład M = {a, b, c, d, e}. Wtedy kombinacja elementów k jest podzbiorem K ⊆ M, który zawiera tylko elementy k. Oczywiście, ponieważ K jest zbiorem, kolejność nie ma znaczenia. Tak więc trójczłonowa kombinacja ze zbioru M może być {a, b, d} lub {b, c, d}.

Różnica z wariacjami polega na tym, że w przypadku wariacji kolejność ma znaczenie, więc [a, b, e] i [e, b, a] są różnymi wariacjami, ale są tą samą kombinacją, ponieważ [a, b, e] i [e, b, a] zawierają te same elementy; to, że są w innej kolejności, nie interesuje nas w przypadku kombinacji.

Możemy jednak użyć wariacji, aby uzyskać wzór na liczbę wszystkich różnych kombinacji. Wiemy, że k-elementowe wariacje zbioru z n elementami to po prostu

$$ V(k, n) = \frac{n!}{(n-k)!}. $$

Jeśli więc policzylibyśmy liczbę wszystkich trójczłonowych wariacji z poprzedniego zbioru M = {a, b, c, d, e}, otrzymalibyśmy V(3, 5) = 60 różnych wariacji. Jednak dla każdej trójki mielibyśmy również wszystkie jej permutacje. Oznacza to, że mielibyśmy tryplet abc, ale także tryplety acb, bac, bca, cab i cba. To sześć różnych wariacji, ale jest to jedna kombinacja, ponieważ wszystkie mają te same elementy.

Jeśli więc mamy trójkę, to ile jest różnych permutacji tej trójki? Tylko 3!. Innymi słowy, istnieje tylko 3! więcej wariacji trójki niż jej kombinacji. Zamiast liczyć na jedną kombinację, liczymy na 3! więcej wariacji, z każdą permutacją danej trójki. Jeśli więc podzielimy liczbę permutacji przez 3!, otrzymamy liczbę kombinacji.

Możemy uogólnić poprzednią procedurę i powiedzieć, że jeśli szukamy liczby wszystkich różnych k-ary kombinacji ze zbioru o rozmiarze n, to ta liczba, oznaczona C(k, n), jest równa,

$$ C(k, n) = \frac{V(k, n)}{k!}, $$

tj. liczba wariacji podzielona przez k!, która jest liczbą permutacji każdej k-tice. Możemy zmodyfikować wzór, dzieląc wzór na obliczanie wariacji:

$$ C(k, n) = \frac{V(k, n)}{k!} = \frac{n!}{(n-k)!}\cdot\frac{1}{k!} = \frac{n!}{(n-k)!\cdot k!}. $$

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

$$ C(2, 3) = \frac{3!}{1!\cdot2!} = 3 $$

a te kombinacje to: {a, b}, {a, c} i {b, c}. Dla kombinacji trójczłonowych z oryginalnego zbioru M = {a, b, c, d, e}, otrzymalibyśmy liczbę

$$ C(3, 5) = \frac{5!}{(5-3)!\cdot3!}=10 $$

i są to następujące 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}.

Liczba kombinacji

Poprzednia notacja wzoru przy użyciu C(k, n) nie jest zbyt często używana i zamiast tego używana jest tak zwana liczba kombinacyjna. Liczba kombinacyjna ma następującą postać

$$ {n \choose k} $$

jest to rodzaj ułamka bez linii ułamkowej (którą i tak z przyzwyczajenia tam wpiszesz), ale z nawiasami (nie są one opcjonalne, muszą tam być). Liczbę kombinowaną odczytujemy jako "en over ka". Wartość numeru kombinacji jest wtedy taka sama jak C(k, n).

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

Tak więc, jeśli mamy zestaw 5 elementów i wybierzemy z niego quady, całkowita liczba elementów wyniesie

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

Podstawowe zależności

Dla liczby kombinacyjnej i n ∈ ℕ zachodzi następująca zależność:

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

Ponadto, dla n, k ∈ ℕ₀ i k ≤ n zachodzi następująca zależność

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

Dla n, k ∈ ℕ₀ i k < n zachodzi następująca zależność

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

Komputer

Poniższy kalkulator obliczy liczbę kombinacyjną n dla k, włączając w to procedurę.

Rozwiązane przykłady

1. Zacznijmy od wspomnianego wcześniej sportu. W tej grze losuje się 6 kul z puli zawierającej 49 kul. Ile różnych możliwości możemy wylosować?

   Po pierwsze - czy kolejność losowania liczb ma znaczenie? Nie ma, zgadujemy tylko liczby, a nie ich kolejność. Użyjemy kombinacji. Mamy w sumie 49 kul, losujemy 6 kul, otrzymujemy kombinację liczb

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

   Istnieje łącznie 13 983 816 możliwości, które można wylosować. Co, nawiasem mówiąc, daje nam prawdopodobieństwo wygranej przy jednym zakładzie 1/13 983 816, czyli 0,00000715112 %.

2. Sagvan, znany podrywacz dziewczyn, jest obecnie na wiejskiej potańcówce, na której jest w sumie 13 pięknych dziewczyn, którymi byłby zainteresowany. Sagvan wie, że jest w stanie uszczęśliwić 4 różne dziewczyny w ciągu jednego wieczoru. Ile różnych czworokątów może wybrać Sagvan?

   To znowu prosty przykład kombinacji, kolejność nie ma znaczenia, Sagvan będzie tak samo dobry z pierwszą dziewczyną, jak z ostatnią. Otrzymujemy więc zestaw 13 dziewczyn, z którego zawsze wybieramy 4 dziewczyny. Prowadzi to do kombinacji liczb

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

3. Masz grupę 50 osób - połowę mężczyzn i połowę kobiet. Ile jest różnych trojaczków osób, jeśli nie mogą one składać się tylko z jednej płci (tj. w trojaczku nie może być trzech mężczyzn ani trzech kobiet).

   To nieco bardziej skomplikowana kombinacja. Jeśli wykluczymy jednopłciowe triady osób, pozostaną nam tylko dwa sposoby, w jakie można utworzyć triadę - dwóch mężczyzn i jedna kobieta lub jeden mężczyzna i dwie kobiety, przy czym liczba kombinacji pierwszej grupy (dwóch mężczyzn i jedna kobieta) jest taka sama jak liczba kombinacji drugiej grupy. Musimy więc tylko obliczyć liczbę kombinacji pierwszej grupy, a następnie pomnożyć ją przez dwa. Teraz znowu wszystko jest proste. Określamy liczbę kombinacji różnych par mężczyzn, która wynosi dwadzieścia pięć przez dwa, i mnożymy ją przez liczbę kombinacji jednej kobiety (co daje dwadzieścia pięć, patrz poprzednia lista liczb kombinacji, a konkretnie pierwsza). Mnożymy ten wynik przez dwa i otrzymujemy wynik końcowy.

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

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

   • aby żaden z nich nie był wadliwy? Obecnie wybieramy 6 produktów spośród 15 − 4 = 11 produktów, które nie są wadliwe. To daje nam liczbę kombinacji

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

   • aby tylko jeden produkt był wadliwy? Wybieramy więc zestaw, który zawiera 5 funkcjonalnych produktów i 1 wadliwy produkt. Mamy 11 funkcjonalnych produktów i 4 wadliwe produkty. Używamy reguły iloczynu kombinatorycznego, aby uzyskać wynik:

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

   • aby co najwyżej jeden był wadliwy? Do rozwiązania wykorzystujemy poprzednie wyniki. Wiemy, że mamy łącznie 462 możliwości wyboru tylko 6 funkcjonalnych produktów i mamy 1848 możliwości wyboru 5 funkcjonalnych i 1 wadliwego produktu. Używamy więc reguły sumy kombinatorycznej, dodajemy te wyniki do siebie i otrzymujemy pożądany wynik, tj. co najwyżej jeden wadliwy produkt (= albo brak wadliwego produktu, albo tylko jeden). Wynikiem jest: 462 + 1848 = 2310.

Źródła i dalsza lektura

• Kombinatoryka na cuni.cz
• Bělohlávek, Vychodil: Matematyka dyskretna [PDF]