Kombinatoryka

Reguła mnożenia to fundament całego działu. Mówi ona, że jeśli pewną czynność wykonujemy etapami, to liczbę wszystkich możliwości otrzymujemy, mnożąc liczby możliwości na każdym etapie.

Jeśli masz $3$ koszulki i $2$ pary spodni, to różnych zestawów ubrań jest $3 \cdot 2 = 6$. Ta prosta zasada wystarcza do rozwiązania większości maturalnych zadań z kombinatoryki.

Silnia to skrócony zapis mnożenia kolejnych liczb naturalnych. Symbol $n!$ oznacza iloczyn $1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$.

Na przykład $4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$. Przyjmujemy też umownie, że $0! = 1$. Silnia bardzo szybko rośnie, więc nawet niewielkie liczby dają duże wyniki.

Permutacja to ustawienie wszystkich elementów zbioru w określonej kolejności. Pytanie brzmi: na ile sposobów można je poustawiać.

Liczbę permutacji zbioru $n$-elementowego liczymy jako $n!$. Pięć osób można ustawić w kolejce na $5! = 120$ sposobów, bo na pierwsze miejsce mamy $5$ kandydatów, na drugie $4$ i tak dalej.

Czasem na każdym etapie mamy do dyspozycji ten sam zestaw możliwości. Wtedy liczbę kombinacji liczymy jako potęgę.

Jeśli kod składa się z $3$ cyfr, a każda może być dowolną z dziesięciu, to wszystkich kodów jest $10^3 = 1000$. To wciąż reguła mnożenia, tylko zapisana krócej.

Najlepsza metoda to wyobrazić sobie, że budujesz wynik krok po kroku. Zastanów się, ile masz możliwości na pierwszej pozycji, ile na drugiej i tak dalej.

Uważaj na jeden szczegół: jeśli elementy nie mogą się powtarzać, liczba możliwości maleje z każdym krokiem. Jeśli mogą, na każdym etapie pozostaje taka sama.