Kombinatoryka

Kombinatoryka - dział matematyki zajmujący się wszystkimi możliwymi, różnorodnymi grupowaniami elementów zbiorów, pojęciami kombinatoryki są: permutacje, kombinacje, wariacje (z powtórzeniami lub bez nich). Kombinatoryka jest wykorzystywana w rachunku prawdopodobieństwa.

Silnia

Zmienna n oznacza liczbę naturalną.

n! = 1 ∙ 2 ∙ 3 ∙ ... ∙ (n - 1) ∙ n, n > 1 - iloczyn kolejnych liczb naturalnych od 1 do n,

0! = 1 oraz 1! = 1

Symbol Newtona definiujemy następująco

Dla symbolu Newtona zachodzą równości:

Permutacje

Permutacją bez powtórzeń zbioru n-elementowego nazywamy każdy ciąg n-wyrazowy utworzony ze wszystkich elementów tego zbioru.

Liczba permutacji bez powtórzeń zbioru n-elementowego

Permutacją z powtórzeniami zbioru n-elementowego nazywamy każdy ciąg n-wyrazowy utworzony z elementów tego zbioru, wśród których pewne elementy powtarzają się odpowiednio n1,n2, … nk razy

Liczba permutacji z powtórzeniami zbioru n-elementowego, wśród których pewne elementy powtarzają się odpowiednio n1,n2, … nk razy

Kombinacje

Kombinacją bez powtórzeń k-elementową ze zbioru n-elementowego (k ≤ n) nazywamy każdy podzbiór k-elementowy tego zbioru.

Liczba kombinacji bez powtórzeń k-elementowych ze zbioru n-elementowego

Wariacje

Wariacje bez powtórzeń k-elementową ze zbioru n-elementowego (k ≤ n) nazywamy każdy k-wyrazowy ciąg różnych elementów tego zbioru

Liczba wariacji bez powtórzeń k-elementowych ze zbioru n-elementowego

Wariacje z powtórzeniami k-elementową ze zbioru n-elementowego (k ≤ n) nazywamy każdy k-wyrazowy ciąg różnych lub nieróżniących się elementów tego zbioru

Liczba wariacji z powtórzeniami k-elementowych ze zbioru n-elementowego

Permutacje, kombinacje, wariacje – zastosowanie

Permutacje

Jeżeli w zadaniu mamy powiedziane, że wykonujemy operacje na wszystkich elementach, wówczas korzystamy z permutacji.

Przykład 1:
Na ile sposobów możemy ustawić 4 książki na półce?

Korzystamy z permutacji

P(4) = 4!= 1*2*3*4 = 24

Jak widzimy, 4 książki można ustawić na półce na 24 sposobów.

Dlaczego użyliśmy permutacji?

Dlatego, że elementami w naszym zadaniu nie były książki, tylko ich różne ustawienia!!!

Kombinacje

Jeżeli z określonych elementów mamy wybrać kilka i kolejność wybranych elementów nie odgrywa roli, wówczas korzystamy z kombinacji.

Przykład 1:
Na ile różnych sposobów możemy wybrać 3 osoby do kina spośród 6.

W tym zadaniu byłoby trudno pokazać, ile tych trójek jest, dlatego po prostu to policzymy.
Ilość osób, jakimi dysponujemy, to 6, czyli n=6, bedziemy wybierali po 3 osoby,zatem k=3. Podstawiamy do wzoru i otrzymujemy:

Dlaczego użyliśmy kombinacji?

Dlatego, że elementami w naszym zadaniu nie jest 6 osób, tylko elementami są różnie wybrane trójki, które pójdą do kina!!!

!!!!!!!!!!!!!!!!!!!!!!Tylko w kombinacjach w wybranych elementach kolejność nie odgrywa roli!!!!!!!!!!!!!!!!!!!!!!!!!!!

Wariacje bez powtórzeń

Jeżeli z określonych elementów mamy wybrać kilka, tak, że nie będą się one powtarzały,ale z treści zadania wynika, że kolejność wybranych elementów odgrywa rolę, wówczas należy skorzystać z wariacji bez powtórzeń.

Przykład 1:
Mamy do dyspozycji 9 drewnianych klocków, na których są pomalowane cyfry od 1 do 9. Ile możemy ułożyć liczb czterocyfrowych,wybierając kolejno bez zwracania 4 klocki?

Rozwiązanie:

Dlaczego użyliśmy wariacji bez powtórzeń?

Dlatego w tym zadaniu wybraliśmy wariacje bez powtórzeń, ponieważ ułożenie naszych czterech klocków będzie ważne. Każde inne ustawienie tych samych klocków zmienia nam liczbę!

Wariacje z powtórzeniami

Jeżeli z określonych elementów mamy wybrać kilka i może się zdarzyć, że wybrane elementy będą się powtarzały, wówczas należy skorzystać z wariacji z powtórzeniami.

Przykład 1:
Na ile sposobów możemy uzyskać różne wyniki, przy rzucie dwiema różnymi kostkami?
Rozwiązanie:
n=6, k=2

Może się tak zdarzyć, że na obu kostkach wypadnie ta sama liczba oczek, zatem uznajemy, że elementy mogą się powtarzać. W tego typu zadaniach należy wiedzieć, że aby odpowiedź była poprawna zakładamy, że te same układy oczek, ale na różnych kostkach, dają inne wyniki, np. (1,5) czy (5,1). W pierwszej sytuacji 1 wypadła na pierwszej kostce natomiast 5 na drugiej. Następna sytuacja pokazuje, że oczka wypadły odwrotnie