Liceum » Pozostałe » Matematyka

Elementy kombinatoryki - podstawy

Kombinatoryka

Kombinatoryka jest teorią obliczania licznych elementów skończonych zbiorów. Powstała przez gry hazardowe, a rozwinęła się dzięki rachunkowi prawdopodobieństwa, teorii informacji, teorii grafów i innym częściom matematyki stosowanej. kombinatoryk jest pozornie odrębną nauką, ponieważ posługuje się specyficzną terminologią. Uczniowie zaczynają się jej uczyć w szkole ze względu na zastosowanie w rachunku prawdopodobieństwa. Kombinatoryka zajmuje się głównie konstrukcją odwzorowań idących z jednego zbioru skończonego do drugiego, ale muszą być spełnione pewne określone warunki oraz znajdowaniem wzorów na ilość tych odwzorowań.

R E K L A M A

czytaj dalej ↓

Permutacja

Permutacja jest odwzorowaniem różnowartościowym skończonego zbioru w siebie.

Liczba permutowań w zbiorze -elementowym dana jest wzorem:

Trzeba odróżnić permutacje wykonywane na zbiorze od permutacji zbioru.

Permutowaniem -elementowego zbioru lub inaczej ustalaniem porządku elementów występujących w tym zbiorze jest każde odwzorowanie różnowartościowe z do .

Oba te pojęcia pokrywają się, gdy .

Kombinacja

Kombinacją nazywamy każdy podzbiór skończonego zbioru.

Kombinacją po jest każdy -elementowy podzbiór zbioru -elementowego ().

Dopełnieniem kombinacji po jest kombinacja po .

Liczba permutacji na kombinacji z po równa jest

Liczba permutacji na kombinacji dopełniającej równa jest

Więc każdej kombinacji po odpowiada permutacji w zbiorze -elementowym.

Jeśli przez oznaczymy liczbę wszystkich kombinacji po ,

to -- liczba wszystkich permutacji w zbiorze -elementowym, mamy:

Symbol jest zastępowany najczęściej przez symbol Newtona .

Wariacja

Wariacją jest odwzorowanie różnowartościowe podzbioru zbioru skończonego w niego samego.

Wariacja po jest odwzorowaniem różnowartościowym -elementowego podzbioru zbioru -elementowego w niego samego.

Liczba wszystkich wariacji po równa się liczbie wszystkich odwzorowań różnowartościowych zbioru w dowolny -elementowy zbiór , tzn. równy liczbie permutacji we wszystkich -elementowych podzbiorach zbioru , czyli we wszystkich kombinacjach po , mamy:

Przykład:

Z cyfr 1,2,3,4 możemy utworzyć liczb trzycyfrowych o różnych cyfrach.

Wariacja z powtórzeniami

Wariacja z powtórzeniami jest każdym odwzorowaniem podzbioru zbioru skończonego w niego samego.

Wariacją z powtórzeniami po jest każde odwzorowanie podzbioru -elementowego zbioru -elementowego w niego samego. Liczba wszystkich wariacji z powtórzeniami po wynosi .

Przykład:

Za pomocą cyfr 1,2,3,4 możemy napisać liczb dwucyfrowych (niekoniecznie muszą być one o różnych cyfrach).

Silnia

Funkcję , określamy w sposób następujący w zbiorze liczb naturalnych: , .

Z powyższego określenia otrzymujemy ,,

Ogólnie dla .

Wartości rosną szybko, np. , , .

Oby obliczyć przybliżoną wartość korzystamy ze wzoru Stirlinga: .

Symbol Newtona

Symbolem Newtona jest funkcja 2 zmiennych, określona następującymi wzorami (gdzie n rzeczywiste i k naturalne).

,

Jeżeli naturalne to symbol Newtona jest równy , tzn. jest to liczba kombinacji po .

Pierwszy raz symbol Newtona wykorzystano przy rozwinięciu funkcji w tzw. szereg potęgowy Newtona: , jest on zbieżny dla .

Na przykład

W związku z tym, że dla naturalnych oraz dla symbol Newtona równy jest , stąd dla szereg potęgowy Newtona upraszcza się do tak zwanego dwumianowego wzoru Newtona: .

W szczególnym przypadku, dla otrzymamy , tzn. jest to liczba wszystkich podzbiorów zbioru -elementowego (razem ze zbiorem pustym i całym zbiorem) równa jest.

Ponieważ i , dla k i n naturalnych oraz takich, że oraz dla naturalnego oraz .

Stąd symbole Newtona tworzą łatwo konstruowalną tablicę trójkątną, nazywaną inaczej trójkątem Pascala:

Każdy kolejny wiersz powstaje w ten sposób, że na brzegach są jedynki, a w środku liczby powstają jako suma dwóch wyrazów występujących bezpośrednio nad nim.