2.2 Kombinatoryka

Często mamy do czynienia ze zbiorami. Gdy elementy zbioru są wypisane, to łatwo możemy znaleĽć ich liczbę. Czasami jednak zbiór jest podany w formie bardziej skomplikowanej i nie jest oczywiste, ile ma ewlementów. Z pomocą przychodzi kombinatoryka - dział matematyki zajmujący się zbiorami skończonymi oraz odwzorowaniami między nimi.
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ń.
Podstawowe pojęcia, którymi posługuje się kominatoryka
Zbiór {x₁ , x₂, ..., x_n} oznacza zbiór o elementach x₁ , x₂, ..., 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₁ , a₂, ..., a_n) oznacza ciąg o wyrazach a₁ , a₂, ..., 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.
Silnia n! oznacza iloczyn kolejnych liczb naturalnych od 1 do n.
n! = 1 · 2 · 3 · ... · n
0! = 1
Symbol Newtona $\left(\begin{array}{c}n\\ k\end{array}\right)$ dla n, k∈N i 0 ≤ k ≤ n oznacza liczbę określoną wzorem
$\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!(n-k)!}$

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 zatem to ilość 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. Elementarną metodą kombinatoryki, często stosowaną intuicyjnie jest również tzw. reguła mnożenia i dodawania.
Mocą zbioru skończonego A nazywamy liczbę jego elementów. Oznaczamy ${\displaystyle \stackrel{=}{A}}$