Kombinatoryka: Permutacje, wariacje i symbol Newtona

Kombinatoryka to matematyczna sztuka zliczania dostępnych opcji bez ich żmudnego wypisywania na kartce. Jak policzyć, na ile sposobów 5 osób może usiąść na 5 krzesłach? Gdybyśmy mieli to rysować, zajęłoby to wieki. Dzięki kombinatoryce, robimy to jednym krótkim działaniem!

1. Silnia i Reguła Mnożenia

Silnia ($n!$) to iloczyn wszystkich kolejnych liczb naturalnych od $1$ aż do $n$. Na przykład $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$. Zapamiętaj jednak kluczowy wyjątek (częsta pułapka na sprawdzianach!), że $0! = 1$.

Reguła mnożenia: Jeśli jedna czynność może zakończyć się na $n$ sposobów, a inna, w pełni niezależna czynność na $m$ sposobów, to obie te czynności następujące po sobie można wykonać na $n \cdot m$ sposobów. (Np. 3 koszule i 4 pary spodni to $3 \cdot 4 = 12$ różnych zestawów ubrań).

Rys. 2. Zasadę mnożenia najłatwiej wyobrazić sobie jako niezależne szufladki. Liczba opcji w każdej szufladce mnoży się przez pozostałe.

2. Trzy najważniejsze operatory

Żeby wiedzieć, którego wzoru powinieneś użyć w zadaniu, musisz zadać sobie dwa absolutnie najważniejsze pytania: czy kolejność ma znaczenie i czy elementy mogą się powtarzać.

Permutacje: Przestawiamy wszystkie zebrane elementy między sobą (niczego nie dobieramy, ani nie odrzucamy). Pytamy: na ile sposobów $n$ osób może ustawić się w kolejce? Odpowiedź: zawsze $n!$.

Rys. 1. Zbiór 3 kul (czerwona, zielona, niebieska) można ustawić w rzędzie na $3! = 6$ różnych sposobów.

Wariacje (kolejność ma znaczenie):
- Z powtórzeniami (np. kod PIN, gdzie cyfry mogą wystąpić wielokrotnie): wybieramy $k$ elementów z puli $n$. Wzór: $n^k$.
- Bez powtórzeń (np. podium wyścigu, ponieważ nie można zająć 1. i 2. miejsca jednocześnie). Wzór: $\frac{n!}{(n-k)!}$.
Kombinacje (kolejność NIE ma znaczenie):
- Tworzenie zespołów roboczych czy losowanie Lotto (nieważne, czy wylosujesz 3, czy 14 jako pierwsze, na końcu liczy się skompletowany kupon). Do tego służy Symbol Newtona.

3. Symbol Newtona

Symbol $\binom{n}{k}$ (czytaj: "n po k") oznacza dokładnie liczbę podzbiorów k-elementowych ze zbioru n-elementowego. Mówiąc prościej: na ile sposobów mogę wybrać $k$ osób z grupy liczącej $n$ osób. Wzór to: $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

4. Przydatne triki i pułapki (Zdarzenie przeciwne i Pułapka z zerem)

Często w zadaniach z kombinatoryki łatwiej jest policzyć to, czego NIE chcemy, niż to co chcemy. To tzw. zdarzenie przeciwne. Jeśli pytanie brzmi "na ile sposobów można wybrać coś tak, by warunek był spełniony co najmniej raz", zazwyczaj najszybciej będzie policzyć WSZYSTKIE możliwości i odjąć od nich te, w których warunek NIE JEST spełniony wcale.

Kolejny klasyk to pułapka z zerem. Przy tworzeniu liczb z podanych cyfr musisz pamiętać, że zero nie może stać na pierwszym miejscu. Dodatkowo, jeśli szukasz liczb parzystych, opłaca się rozdzielić zadanie na dwa przypadki: "zero jest ostatnie" oraz "zero nie jest ostatnie" (ponieważ zero na końcu automatycznie gwarantuje parzystość, a zero w środku blokuje nam inne opcje).

Dla dociekliwych: Skąd to się wzięło?

Zastanawiałeś się kiedyś, dlaczego słynny Symbol Newtona (kombinacje) ma taki, a nie inny wzór? Skąd wzięły się w nim aż trzy silnie? Prześledźmy to logicznie!

Wyobraź sobie, że masz klasę liczącą 30 uczniów ($n = 30$) i musisz z niej wybrać 3 osoby do samorządu szkolnego ($k = 3$).

Pierwszą osobę do samorządu możesz wybrać na 30 sposobów.
Drugą już tylko na 29 sposobów.
Trzecią na 28 sposobów. Zgodnie z regułą mnożenia, mamy więc $30 \cdot 29 \cdot 28$ opcji wyboru. Zauważ, że jest to początek rozpisanej silni z 30! Brakuje tam jednak całej końcówki (od 27 w dół do 1). Matematycznie ten fragment zapiszemy jako $\frac{30!}{27!}$ (ponieważ 27! w mianowniku "skróci" nam wszystkie liczby od 27 w dół z licznika, zostawiając samo $30 \cdot 29 \cdot 28$). Ogólny wzór na to "ucinanie" silni to: $\frac{n!}{(n-k)!}$. Tak właśnie powstaje wzór na wariacje bez powtórzeń (ponieważ w samorządzie jedna osoba mogłaby być np. Przewodniczącym, druga Zastępcą, a trzecia Skarbnikiem – kolejność wyboru dawała im inne role).

Co jednak, jeśli wybieramy po prostu 3 osoby do sprzątania sali, gdzie funkcja każdego z nich jest identyczna? Wtedy trójka uczniów "Kasia, Tomek, Ania" to dokładnie ten sam zespół co "Ania, Kasia, Tomek"! Ile jest takich powtarzających się "przestawień" dla 3 osób? Zgodnie z zasadą permutacji, dokładnie $3!$ (czyli 6). Zatem nasz poprzedni wynik musimy dodatkowo podzielić przez $3!$, żeby usunąć z niego te powtarzające się, identyczne grupy.

Ogólnie dzielimy przez $k!$. Gdy połączymy to wszystko w całość: bierzemy wariacje bez powtórzeń $\frac{n!}{(n-k)!}$ i dzielimy jeszcze przez $k!$, otrzymując finalny wzór na kombinacje: $\frac{n!}{k!(n-k)!}$. Oto słynny Symbol Newtona, który pozwala stworzyć zespół pomijając całkowicie sztuczną kolejność losowania!