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 {x1 , x2, ..., xn} oznacza zbiór o elementach x1 , x2, ..., xn. 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 (a1 , a2, ..., an) oznacza ciąg o wyrazach a1 , a2, ..., an. 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 n k dla n, kN i 0 ≤ kn oznacza liczbę określoną wzorem
n k = 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 A=


Twierdzenie o mnożeniu
Permutacje
Wariacje
Kombinacje



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

kombinatoryka

matematyka » algebra » kombinatoryka




gość logowanie

© 2014 Mariusz Śliwiński      mapa | o serwisie | kontakt | rss online: 32 drukuj