Kombinatoryka

Kombinatoryka odpowiada na pytanie „na ile sposobów?", zanim ktokolwiek zdąży zacząć wypisywać przypadki. Jest też warunkiem wstępnym prawdopodobieństwa klasycznego: żeby podzielić liczbę zdarzeń sprzyjających przez liczbę wszystkich, trzeba najpierw umieć obie policzyć.

Reguła mnożenia

Cała kombinatoryka wyrasta z jednej obserwacji. Jeśli wybór składa się z kilku niezależnych kroków, a kolejne kroki dają $k_1, k_2, \ldots, k_m$ możliwości, to wszystkich wyników jest:

Możliwości mnożymy, a nie dodajemy — bo każdą decyzję z pierwszego kroku da się połączyć z każdą decyzją z drugiego.

Silnia

Iloczyn kolejnych liczb naturalnych pojawia się w kombinatoryce tak często, że dostał własny symbol:

Czyta się to „n silnia". Kilka pierwszych wartości warto znać na pamięć:

Uwaga na pierwszą kolumnę: $0! = 1$, z definicji. Pusty ciąg można ustawić dokładnie na jeden sposób — nie robiąc nic — a poza tym bez tej umowy wzory na kombinacje dzieliłyby przez zero.

Ten wzrost jest praktyczną wskazówką: skoro dziesięć osób da się ustawić na $3\,628\,800$ sposobów, nie ma mowy o rozwiązywaniu zadań przez wypisywanie przypadków.

Permutacje

Permutacja to ustawienie wszystkich $n$ elementów w kolejności. Pierwsze miejsce można obsadzić na $n$ sposobów, drugie na $n-1$ (jeden element już zużyty), i tak dalej:

Wariacje bez powtórzeń

Gdy z $n$ elementów wybieramy tylko $k$, ale kolejność ma znaczenie, mówimy o wariacjach bez powtórzeń:

Druga postać jest wygodniejsza w rachunku: to po prostu $k$ malejących czynników, zaczynając od $n$.

Wariacje z powtórzeniami

Jeśli elementy wolno powtarzać, każdy z $k$ kroków ma pełne $n$ możliwości, więc reguła mnożenia daje wprost:

Kombinacje

Gdy wybieramy $k$ elementów z $n$, a kolejność nie ma znaczenia, mamy kombinacje:

Skąd bierze się $k!$ w mianowniku? Stąd, że każdy $k$-elementowy zbiór został policzony we wariacjach $k!$ razy — raz dla każdego ustawienia tych samych elementów. Dzielimy więc przez liczbę tych ustawień:

Symetria

Kombinacje mają własność, która oszczędza mnóstwo rachunku:

Wybranie $k$ elementów to przecież to samo, co wskazanie $n-k$ elementów, które zostawiamy. Dlatego $\binom{20}{18}$ liczy się jak $\binom{20}{2} = 190$, a nie przez rozpisywanie osiemnastu czynników.

Suma wszystkich słupków wynosi $64 = 2^6$ — tyle jest podzbiorów zbioru sześcioelementowego, bo o każdym elemencie decydujemy niezależnie: brać czy nie brać.

Trójkąt Pascala

Symbole $\binom{n}{k}$ dla kolejnych $n$ układają się w trójkąt, w którym nie trzeba liczyć ani jednej silni. Wiersze numerujemy od zera:

Reguła budowy jest jedna: każdy wiersz zaczyna się i kończy jedynką, a każdy wyraz w środku jest sumą dwóch stojących nad nim. Zapisana symbolami, jest to tożsamość:

Dlaczego działa? Wskaż jeden ustalony element zbioru — powiedzmy pierwszy. Każdy $k$-elementowy wybór albo go bierze (zostaje $k-1$ miejsc do obsadzenia spośród $n-1$ pozostałych elementów), albo go pomija (wszystkie $k$ miejsc trzeba obsadzić spośród $n-1$). Te dwa przypadki nie mają części wspólnej i wyczerpują wszystkie możliwości, więc liczby się dodają.

Trójkąt pokazuje przy okazji dwie własności, które już znamy, tyle że na rysunku. Symetria $\binom{n}{k} = \binom{n}{n-k}$ to lustrzane odbicie wiersza względem jego środka. A suma wyrazów wiersza $n$ wynosi $2^n$ — wiersz szósty to dokładnie $1, 6, 15, 20, 15, 6, 1$ z wykresu wyżej, sumujący się do $64$.

Dwumian Newtona

Trójkąt nie jest ciekawostką — to tablica współczynników potęgi sumy. Wzór dwumianowy mówi:

Uzasadnienie jest znów kombinatoryczne, a nie rachunkowe. Potęga $(a+b)^n$ to iloczyn $n$ jednakowych nawiasów; wymnażając je, z każdego nawiasu bierzemy albo $a$, albo $b$. Składnik z $b^k$ powstaje dokładnie wtedy, gdy $b$ wzięliśmy z $k$ nawiasów spośród $n$ — a takich wyborów jest $\binom{n}{k}$. Stąd współczynnik.

W praktyce nie sumuje się tego symbolicznie, tylko odczytuje $n$-ty wiersz trójkąta. Dla $n = 4$ jest to $1, 4, 6, 4, 1$:

Zwróć uwagę na dwa niezależne rytmy: wykładnik przy $a$ maleje od $n$ do zera, wykładnik przy $b$ rośnie od zera do $n$, a ich suma w każdym składniku jest równa $n$. To najszybszy test poprawności rozwinięcia. Wzory skróconego mnożenia na $(a+b)^2$ i $(a+b)^3$ to po prostu wiersze drugi i trzeci tego samego trójkąta.

Który wzór wybrać

Cała trudność sprowadza się do dwóch pytań o treść zadania:

Praktyczny test na pierwsze pytanie: zamień miejscami dwa wybrane elementy. Jeśli powstała inna sytuacja — kolejność ma znaczenie.

Ćwiczenia

Pięć typów pytań odpowiada pięciu wzorom z tabeli powyżej — trójkąt Pascala i dwumian Newtona ćwiczy się na przykładach z tamtych sekcji, bo generator pyta tu o liczbę sposobów, a nie o wiersz ani o współczynnik. Prompt z wykrzyknikiem prosi wprost o silnię — pamiętaj o $0! = 1$. Permutacje dla danego $n$ to również $n!$, tylko zadane słowem. Wariacje bez powtórzeń i wariacje z powtórzeniami dostają oba parametry, $n$ i $k$; różnią się tylko tym, czy elementy wolno brać wielokrotnie. Kombinacje pytają o wybór $k$ z $n$ bez znaczenia kolejności — i tu warto pamiętać o symetrii. Każda odpowiedź jest liczbą całkowitą.

Częste błędy

• Dodawanie zamiast mnożenia — kolejne kroki wyboru mnożą liczby możliwości.
• Mylenie wariacji z kombinacjami — jeśli kolejność nie ma znaczenia, wynik trzeba jeszcze podzielić przez $k!$.
• Zapomniane $0! = 1$ — zwłaszcza w skrajnych przypadkach wzoru na kombinacje.
• Skracanie silni „na oko" — $\tfrac{8!}{5!}$ to $8 \cdot 7 \cdot 6$, a nie $\tfrac{8}{5}$ ani $3!$.
• Powtórzenia wzięte z sufitu — o tym, czy elementy mogą się powtarzać, rozstrzyga treść zadania, a nie wygoda wzoru.
• Wypisywanie przypadków — przy $n$ większym od pięciu jest ich zwykle za dużo, żeby zdążyć się nie pomylić.
• Przesunięty wiersz trójkąta — wiersz numer $n$ ma $n+1$ wyrazów i numeruje się je od zera, więc $\binom{5}{2}$ to trzeci wyraz piątego wiersza, a nie drugi.
• Sam współczynnik zamiast całego wyrazu — w rozwinięciu $(x+2)^5$ przy $x^3$ stoi $\binom{5}{2} \cdot 2^2 = 40$, a nie samo $\binom{5}{2} = 10$: potęgowana jest cała dwójka, nie tylko $x$.