Kombinatoryka

Reguła mnożenia i reguła dodawania

Reguła mnożenia (nazywana też regułą iloczynu) pozwala policzyć, ile jest wszystkich możliwych sposobów wykonania złożonego zadania, które składa się z kilku etapów – jeśli na każdy z nich mamy określoną liczbę możliwości. Każda decyzja nie zależy od poprzednich (czyli wybory są niezależne).

Reguła dodawania to zasada, która pomaga policzyć łączną liczbę sposobów wykonania zadania, gdy mamy kilka rozłącznych opcji do wyboru. Jeśli coś można zrobić na jeden z kilku różnych sposobów, i żaden z nich się nie pokrywa (nie zachodzi jednocześnie), to sumujemy liczby możliwości. Nie wolno dodawać opcji, które mogą wystąpić jednocześnie – wtedy to już inna bajka, np. reguła mnożenia!

Wariacje to rodzaj ułożenia elementów, gdzie ma znaczenie kolejność, wybieranie tylko części elementów z większego zbioru.

Wariacją k – wyrazową z powtórzeniami  n – elementowego zbioru A jest równa

Wariacją k – wyrazową bez powtórzeń n – elementowego zbioru A jest równa

Permutacją bez powtórzeń n- elementowego zbioru A, nazywamy każdy n- wyrazowy ciąg utworzony ze wszystkich elementów zbioru A.

Liczba permutacji bez powtórzeń zbioru n- elementowego jest równa

Silnia

n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1  
0! = 1 \qquad 1!=1 

Kombinacje

Kombinacją k- elementową bez powtórzeń n- elementowego zbioru A, nazywamy każdy k – elementowy podzbiór zbioru A, przy czym elementy zbioru A nie mogą się powtórzyć.

Liczbę  k- elementowych kombinacji bez powtórzeń zbioru n-elementowego jest równa

Symbol Newtona. Wzór Newtona