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ń.

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.