Kombinatoryka

Kombinatoryka zajmuje się wyznaczaniem liczby elementów zbiorów skończonych utworzonych zgodnie z określonymi zasadami. Najważniejszym jej zadaniem jest konstruowanie spełniających pewne określone warunki odwzorowań jednego zbioru skończonego w drugi oraz znajdowanie wzorów na liczbę tych odwzorowań. Swój rozwój zawdzięcza rachunkowi prawdopodobieństwa, gdzie znajduje szerokie zastosowanie przy wyznaczaniu liczebności zdarzeń elementarnych.

Kombinatoryka odpowiada na pytanie, ile da się zbudować odwzorowań określonego rodzaju z dostępnych elementów. Wyróżniamy trzy rodzaje takich odwzorowań: permutacje, wariacje i kombinacje.

Wzajemnie jednoznaczne przekształcenie pewnego zbioru skończonego na siebie nazywamy permutacją. Permutacja to liczba możliwych przestawień pewnego zbioru w różne ciągi. Ciąg $k$-elementowy powstały ze zbioru $n$-elementowego to wariacja, w której ważna jest kolejność elementów. Jedna z możliwości wyboru kilku elementów z pewnego zbioru to kombinacja, przy czym kolejność wyboru elementów nie ma znaczenia.

Należy pamiętać, że w wariacji liczy się kolejność ustawienia wyrazów, a kombinacja to tylko zbiór elementów.

Pomocnym w zrozumieniu różnic między permutacją, wariacją a kombinacją może być poniższy schemat i przykład pod nim.

Rozważmy trzyelementowy zbiór $\{ A, B, C \}$ i zbudujmy wszystkie trzywyrazowe ciągi (permutacje), dwuwyrazowe ciągi (wariacje) oraz dwuelementowe podzbiory (kombinacje).
- permutacje: $ABC, ACB, BAC, BCA, CAB, CBA$
- dwuwyrazowe wariacje: $AB, AC, BA, BC, CA, CB$
- dwuelementowe kombinacje: $\{ A,B\}, \{A,C\}, \{B,C\}$

Zbiór $\{x_1 , x_2, \ldots, x_n\}$ oznacza zbiór o elementach $x_1 , x_2, \ldots, x_n$. Każdy zbiór nie zawiera dwóch identycznych elementów, to znaczy każdy element traktujemy tak, jakby występował tylko jeden raz, a kolejność elementów zbioru nie odgrywa roli.

Multizbiór - to zbiór, który może zawierać elementy identyczne, a więc każdy z różnych elementów multizbioru może występować więcej niż jeden raz.

Ciąg $(a_1 , a_2, \ldots, a_n)$ oznacza ciąg o wyrazach $a_1 , a_2, \ldots, a_n$. Kolejność ustawienia wyrazów w ciągu jest bardzo ważna. Zmieniając kolejność wyrazów w ciągu otrzymujemy inny ciąg. Ciąg może zawierać wyrazy identyczne lub nie.

Mocą zbioru skończonego $A$ nazywamy liczbę jego elementów i oznaczamy $|A|$ lub $ {\overset {\mbox{=}}{A}}$.

Symbol $n!$ oznacza iloczyn kolejnych liczb naturalnych od $1$ do $n$ i nosi nazwę silni. $n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$.

Symbol Newtona $\binom{n}{k}$ dla $n, k \in N$ i $0 \le k \le n$ oznacza liczbę określoną wzorem $\binom{n}{k} = \frac{n!}{k!(n - k)!}$.

Silnia
Symbol Newtona

Reguła mnożenia
Reguła dodawania

Permutacje
Wariacje
Kombinacje