Kombinatoryka

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ń).

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!$.
• 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 znaczenia):
  • 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)!} $$

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!

Przykładowe zadania