Kombinatoryka

Chcesz wiedzieć, ile różnych piątek kart możesz wybrać z talii 32 kart? To właśnie typowe zadanie, którym zajmuje się kombinatoryka. Istnieją dwie podstawowe reguły kombinatoryczne — reguła dodawania i reguła mnożenia. Wszystkie pozostałe metody są tylko rozwinięciem tych dwóch zasad.

Reguła dodawania

Reguła dodawania jest bardzo prosta — mówi, że jeśli mamy zbiory A, B, które nie mają żadnego wspólnego elementu, to liczba wszystkich możliwych sposobów wyboru jednego elementu z sumy A ∪ B jest równa |A| + |B|, czyli sumie liczb elementów obu zbiorów.

Zacznijmy od łatwego przykładu. Mamy 6 czerwonych piłeczek i 8 niebieskich piłeczek. Wsypujemy je wszystkie do jednej urny. Ile mamy w sumie możliwości, jeśli losujemy jedną piłeczkę? Na początku mieliśmy zbiór czerwonych piłeczek, oznaczmy go jako zbiór A, oraz zbiór niebieskich piłeczek, oznaczmy go B. Te zbiory są rozłączne, to znaczy nie mają żadnej wspólnej piłeczki. Chcemy wylosować jedną piłeczkę, więc mamy w sumie |A| + |B| = 6 + 8 = 14 możliwości. To wszystko.

Reguła mnożenia

Znowu mamy dwa zbiory, K i M. Zbiór K zawiera trzy kobiety, a zbiór M czterech mężczyzn. Pytamy, ile różnych par mężczyzna–kobieta możemy z tych zbiorów utworzyć. Co właściwie robimy — zawsze bierzemy jedną kobietę i przydzielamy jej jakiegoś mężczyznę. Liczbę wszystkich par obliczymy tak: bierzemy jedną kobietę, Kasię, i po kolei przydzielamy jej wszystkich mężczyzn. Otrzymujemy w ten sposób 4 różne pary, bo możemy jej przydzielić łącznie 4 różnych panów. To samo robimy dla pozostałych dwóch kobiet, każda z nich również utworzy kolejne 4 pary. I to wszystko, mamy w sumie 4 + 4 + 4 = 12 par.

Co właściwie zrobiliśmy? Pomnożyliśmy liczby elementów obu zbiorów. Mieliśmy 3 panie i 4 panów, więc liczba wszystkich par wynosi 3 · 4 = 12. Stąd nazwa: reguła mnożenia. Jeśli więc mamy dwa zbiory, z których tworzymy pary, to po prostu mnożymy liczbę elementów jednego zbioru przez liczbę elementów drugiego zbioru.

Poniżej możesz sprawdzić, że to naprawdę działa. Oto wszystkie pary, jakie możemy utworzyć z 3 kobiet i 4 mężczyzn. Każdy wiersz przedstawia możliwości dla jednej z kobiet, a każda kolumna możliwości dla jednego z panów. Mamy więc trzy wiersze i cztery kolumny, czyli łącznie $\text{wiersze} \cdot \text{kolumny}$ możliwości.

$$\begin{eqnarray} &&(K_1, M_1), (K_1, M_2), (K_1, M_3), (K_1, M_4), \\ &&(K_2, M_1), (K_2, M_2), (K_2, M_3), (K_2, M_4), \\ &&(K_3, M_1), (K_3, M_2), (K_3, M_3), (K_3, M_4) \end{eqnarray}$$

Rozwiązane przykłady

1. Ile istnieje różnych liczb dwucyfrowych? Jak wygląda taka liczba dwucyfrowa? Na pierwszym miejscu stoi jedna z cyfr 1, …, 9, natomiast na drugim miejscu może pojawić się dodatkowo zero: 0, …, 9. W pierwszym zbiorze mamy więc 9 cyfr, w drugim 10. Stosujemy regułę mnożenia i otrzymujemy wynik: 9 · 10 = 90.

• Ile istnieje różnych liczb trzycyfrowych, w których żadna cyfra nie może wystąpić dwa razy? Na pierwszym miejscu znowu może stać dziewięć cyfr, bo liczba nie może zaczynać się od zera. Na drugim miejscu mogą stać wszystkie cyfry łącznie z zerem, ale nie może tam stać cyfra z pierwszej pozycji, więc od dziesięciu możliwych cyfr odejmujemy jedynkę (jeśli na przykład nasza liczba trzycyfrowa zaczyna się akurat czwórką, to jasne, że na drugiej pozycji czwórka już stać nie może, bo w całej liczbie wystąpiłaby dwa razy). Na trzecim miejscu znowu mogą stać wszystkie cyfry, ale nie może tam stać cyfra, która jest na pierwszym lub na drugim miejscu. Powód jest ten sam. Jeśli na pierwszym miejscu jest cyfra 4, a na drugim cyfra 7, to na trzecie miejsce możemy wstawić jedną cyfrę ze zbioru {0, …, 9} ∖ {4, 7}. Od dziesięciu cyfr musimy więc odjąć dwójkę. Teraz wystarczy pomnożyć 9 · 9 · 8 = 648. Takich liczb jest więc 648.
• Rzucamy dwa razy z rzędu zwykłą kostką do gry. Ile różnych wyników możemy otrzymać? W pierwszym rzucie może wypaść 6 różnych wyników. W drugim rzucie również, więc łączna liczba możliwości wynosi 6 · 6 = 36.
• Rzucamy dwa razy z rzędu kostką. Ile różnych wyników możemy otrzymać, jeśli w pierwszym rzucie wypadła liczba parzysta? W pierwszym rzucie wypadła liczba parzysta, czyli jedna z liczb 2, 4, 6, co daje 3 możliwości. W drugim rzucie może już wypaść dowolna liczba, więc w sumie mamy 3 · 6 = 18 możliwości.