Kombinatoryka

Kombinatoryka to teoria obliczania liczby elementów w zbiorach skończonych. Rozwój kombinatoryki zawdzięczamy... a jakże, grom hazardowym, a także rachunkowi prawdopodobieństwa, teorii grafów, teorii informacji i innym działom matematyki. Stanowi jeden z działów tak zwanej matematyki dyskretnej. Podstawowymi pojęciami kombinatoryki są: permutacje, kombinacje, wariacje (z powtórzeniami lub bez). Kombinatoryka jest głównym narzędziem rachunku prawdopodobieństwa.

Podstawowe pojęcia występujące w kombinatoryce

Silnia

Niech n oznacza

liczbę naturalną. Definiujemy n silnia (i oznaczamy n!) jako:

0! = 1

n! = 1 · 2 · 3 · ... · (n - 1) · n, n ≥ 1

Obrazowo mówiąc jest to po prostu iloczyn kolejnych liczb naturalnych od 1 do n. n! wyraża liczbę możliwych ustawień zbioru n-elementowego. Przykładowo, z cyfr od 1 do 5 można ułożyć 1·2·3·4·5 = 120 różnych liczb (wykorzystując jedną cyfrę tylko raz).

Symbol Newtona

Symbol Newtona jest liczbą możliwości w jaki możemy ze zbioru n-elementowego utworzyć zbiór k-elementowy. Definiujemy go następująco:

Symbol Newtona

gdzie k, n ∈ N, 0 ≤ k ≤ n

Przykładowo: na ile różnych sposobów możemy wybrać 3 kapelusze spośród 6? Zbiór n-elementowy to nasz zbiór kapeluszy. Zatem n=6, bedziemy wybierali za każdym razem 3 kapelusze, zatem k=3. Otrzymujemy: zatem n!/k!(n-k)! = 6!/3!(6-3)! = 20. Zatem na 20 sposobów. Sporo...

Bodaj najpiękniejszym zastosowaniem symbolu Newtona jest tzw. dwumian Newtona. Chodzi o n-tą potęgę sumy. Wzór na kwadrat i sześcian sumy mamy w małym palcu. Okazuje się, że:

Dwumian Newtona

Permutacje (bez powtórzeń i z powtórzeniami)

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ń Pn zbioru n-elementowego wynosi właśnie n!.

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:

Permutacje z powtórzeniami

Kombinacje

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

Liczba kombinacji k-elementowych ze zbioru n-elementowego wynosi:

Kombinacje

Przykład: Patrz symbol Newtona.

Wariacje bez powtórzeń

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 bez powtórzeń

Jeżeli z określonych elementów mamy wybrać kilka, tak, że nie będą się one powtarzały, ale odgrywa rolę kolejność wybranych elementów , wówczas należy skorzystać z wariacji bez powtórzeń. Na przykład mamy do dyspozycji 9 kulek, na których znajdują się cyfry od 1 do 9. Ile możemy ułożyć liczb czterocyfrowych, losując kolejno bez zwracania 4 kulki? Podstawiając n = 9, k = 4 otrzymujemy 3024 możliwości. Gdyby kolejność wylosowanych cyfr nie odgrywała roli wówczas musielibyśmy rezultat podzielić przez 4! czyli 24, otrzymując 126.

Wariacje z powtórzeniami

Wariacją k-elementową z powtórzeniami 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:

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 użyć wariacji z powtórzeniami. Na przykład: na ile sposobów możemy uzyskać różne wyniki, przy rzucie dwiema różnymi kostkami? Podstawiając n = 6 i k = 2 otrzymujemy 36 sposoby. 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, 4) i (4, 1). W pierwszej sytuacji 1 wypadła na pierwszej kostce natomiast 4 na drugiej. W drugiej sytuacji było odwrotnie.

Kombinatoryka posługuje się terminologią nie występującą w innych działach matematyki, stąd pozorna jest od niej odrębna. Ale jak większość rzeczy w matematyce, ta odrębność jest tylko pozorna.

GÓRA         SZKOŁA         

©2007-2016 Łukasz Ługowski, Młodzieżowy Ośrodek Socjoterapii nr 2 „KĄT”. Wykonanie:
Licencja Creative Commons - zdjęcia, rysunki i obrazy należą do uczniów i pracowników MOSu „KĄT”; kilka przyjaciół i znajomych

Podziękowania: Uczniowie, nauczyciele & „KĄTowi” przyjaciele!