logowanie

matematyka » algebra » kombinatoryka

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.



Tabela przedstawiająca algorytm postępowania przy rozwiązywaniu zadań.

kombinatoryka





© 2016 Mariusz Śliwiński      o serwisie | kontakt online: 26 drukuj