Kombinatoryka

Reguła mnożenia mówi, że jeśli pewną czynność wykonujemy w kilku etapach po kolei, a na pierwszym etapie mamy k1 możliwości, na drugim k2 możliwości i tak dalej, przy czym liczba możliwości na każdym kolejnym etapie nie zależy od tego, który wariant wybraliśmy wcześniej, to całą czynność można wykonać na iloczyn tych liczb sposobów. Klasycznym przykładem jest wybór stroju złożonego z koszulki i spodni, gdzie mając 4 koszulki i 3 pary spodni, otrzymujemy 4 · 3 = 12 możliwych zestawów. Reguła mnożenia stosuje się więc nie tylko wtedy, gdy kolejne wybory są od siebie całkowicie niezależne, ale też wtedy, gdy same dostępne opcje zmieniają się po każdym wyborze, o ile ich liczba na każdym etapie jest z góry taka sama, tak jak przy wybieraniu kolejnych elementów bez powtórzeń. Jest to najbardziej podstawowe narzędzie kombinatoryki, na którym opierają się właściwie wszystkie pozostałe wzory, ponieważ permutacje, wariacje czy kombinacje można wyprowadzić właśnie z wielokrotnego zastosowania reguły mnożenia.

Reguła dodawania stosuje się wtedy, gdy interesujący nas wynik można osiągnąć na jeden z kilku wzajemnie wykluczających się sposobów, i chcemy policzyć, ile jest wszystkich możliwości łącznie. Jeśli pierwszy sposób postępowania daje k1 możliwości, a drugi, całkowicie od niego różny, daje k2 możliwości, i żadna z tych możliwości nie powtarza się w obu zbiorach, to łączna liczba możliwości to k1 + k2. Przykładowo, jeśli na obiad wybieramy albo jedno z 3 dań mięsnych, albo jedno z 2 dań wegetariańskich, to mamy w sumie 3 + 2 = 5 możliwości wyboru dania. Kluczowa różnica między regułą dodawania a regułą mnożenia polega na tym, czy wykonujemy jedną czynność wybraną spośród kilku wariantów, wtedy dodajemy, czy kilka czynności po kolei, wtedy mnożymy.

Permutacja zbioru n różnych elementów to każde możliwe ustawienie tych elementów w ciąg, czyli nadanie im kolejności. Liczbę wszystkich permutacji zbioru n-elementowego oznaczamy Pₙ i obliczamy jako Pₙ = n!, czyli iloczyn wszystkich liczb naturalnych od 1 do n. Wynika to wprost z reguły mnożenia, ponieważ na pierwsze miejsce w ciągu możemy wstawić dowolny z n elementów, na drugie miejsce dowolny z pozostałych n − 1 elementów, i tak dalej, aż na ostatnie miejsce zostaje już tylko jeden element. Na przykład liczba sposobów ustawienia 4 różnych książek na półce to 4! = 24. Permutacje stosujemy zawsze wtedy, gdy bierzemy wszystkie elementy danego zbioru i zmieniamy jedynie ich kolejność, bez pomijania żadnego elementu i bez powtórzeń.

Wariacja bez powtórzeń k-elementowa ze zbioru n-elementowego to uporządkowany wybór k różnych elementów spośród n dostępnych, gdzie k jest mniejsze lub równe n. W odróżnieniu od permutacji nie wykorzystujemy tu wszystkich elementów zbioru, tylko wybieramy ich część, ale liczy się zarówno to, które elementy wybraliśmy, jak i w jakiej kolejności je ustawiliśmy. Liczbę takich wariacji liczymy ze wzoru W(n, k) = n! / (n − k)!, co odpowiada wybieraniu kolejno pierwszego elementu na n sposobów, drugiego na n − 1 sposobów, i tak dalej przez k kroków. Typowym przykładem jest ułożenie podium zawodów, gdzie spośród 10 zawodników wybieramy trzech na miejsca pierwsze, drugie i trzecie, co daje 10 · 9 · 8 = 720 możliwości, ponieważ zamiana zawodników miejscami daje inny wynik.

Wariacja z powtórzeniami k-elementowa ze zbioru n-elementowego to uporządkowany ciąg długości k, w którym każdy element zbioru może zostać wybrany więcej niż raz. Liczbę takich wariacji obliczamy jako n^k, ponieważ na każde z k miejsc w ciągu mamy do wyboru wszystkie n elementów, niezależnie od tego, co wybraliśmy na poprzednich miejscach. Typowym przykładem jest ustalenie czterocyfrowego kodu PIN, gdzie na każdej z 4 pozycji może pojawić się dowolna cyfra od 0 do 9, co daje 10^4 = 10 000 możliwych kodów, mimo że cyfry mogą się powtarzać, na przykład kod 1122 jest tak samo dopuszczalny jak 1234. Wariacje z powtórzeniami stosujemy zawsze, gdy kolejność ma znaczenie i jednocześnie nic nie zabrania powtarzania tego samego elementu na różnych pozycjach.

Kombinacja k-elementowa ze zbioru n-elementowego to wybór k elementów spośród n dostępnych, w którym nie liczy się kolejność, a jedynie to, jakie elementy znalazły się w wybranym podzbiorze. Liczbę kombinacji oznaczamy symbolem Newtona C(n, k) i obliczamy jako C(n, k) = n! / (k! · (n − k)!). Wzór ten można otrzymać z liczby wariacji bez powtórzeń, dzieląc ją przez k!, ponieważ każdy k-elementowy podzbiór można ustawić na k! różnych sposobów, a nas interesuje tylko sam podzbiór, bez rozróżniania kolejności. Klasycznym przykładem jest losowanie 6 liczb spośród 49 w grze liczbowej, gdzie kolejność wylosowanych liczb nie ma znaczenia, więc liczbę możliwych zestawów liczymy jako C(49, 6). Kombinacje stosujemy zawsze, gdy wybieramy grupę elementów, a kolejność wyboru jest nieistotna.

Silnia liczby naturalnej n, zapisywana jako n!, to iloczyn wszystkich liczb naturalnych od 1 do n, a dodatkowo przyjmujemy umownie, że 0! = 1, co jest potrzebne, by wzory kombinatoryczne działały poprawnie także dla skrajnych przypadków, na przykład wyboru zera elementów. Symbol Newtona C(n, k) oznacza liczbę kombinacji i ma kilka naturalnych własności ułatwiających obliczenia. C(n, 0) = C(n, n) = 1, ponieważ istnieje dokładnie jeden sposób, by wybrać żadnego elementu albo wybrać wszystkie elementy. C(n, k) = C(n, n − k), co odpowiada temu, że wybór k elementów do grupy jest równoważny wyborowi n − k elementów, które w grupie się nie znajdą. Te własności pozwalają szybko sprawdzić poprawność obliczeń bez wykonywania pełnego dzielenia silni.

Największą trudnością w kombinatoryce nie jest zapamiętanie wzorów, tylko rozpoznanie, który z nich pasuje do konkretnej sytuacji, dlatego warto zadawać sobie po kolei dwa pytania. Pierwsze pytanie brzmi, czy kolejność wybranych elementów ma znaczenie, czyli czy zamiana dwóch elementów miejscami daje inny wynik. Jeśli tak, rozważamy permutacje albo wariacje, jeśli nie, rozważamy kombinacje. Drugie pytanie brzmi, czy elementy mogą się powtarzać, czy każdy element może zostać użyty tylko raz. Gdy kolejność ma znaczenie i bierzemy wszystkie elementy bez powtórzeń, stosujemy permutacje. Gdy kolejność ma znaczenie i bierzemy tylko część elementów bez powtórzeń, stosujemy wariacje bez powtórzeń, a gdy powtórzenia są dozwolone, wariacje z powtórzeniami. Gdy kolejność nie ma znaczenia, niezależnie od tego, ile elementów wybieramy, stosujemy kombinacje. Różnicę dobrze widać na grupie 5 osób, z której wybieramy 2: jeśli przydzielamy im różne stanowiska, prezesa i wiceprezesa, kolejność ma znaczenie i liczba możliwości to 5 · 4 = 20, natomiast jeśli wybieramy z tej samej grupy dwuosobowy zespół bez podziału na role, kolejność nie ma znaczenia i liczba możliwości to C(5, 2) = 10, czyli dokładnie dwa razy mniej, ponieważ każdą wybraną parę osób można ustawić na 2! sposoby.