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 elementó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ę kombinatoryka.
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.
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)!}$.
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 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.
Elementarną metodą kombinatoryki, często stosowaną intuicyjnie jest również tzw. reguła mnożenia i dodawania.
Twierdzenie o mnożeniu
Silnia
Symbol Newtona
Permutacje
Wariacje
Kombinacje
Tabela przedstawiająca algorytm postępowania przy rozwiązywaniu zadań.
