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:

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:

Rozpisując to na składniki mamy:

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ń P_n 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 n₁,n₂, ... n_k razy.

Liczba permutacji z powtórzeniami zbioru n-elementowego, wśród których pewne elementy powtarzają się odpowiednio n₁,n₂, ... n_k razy:

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:

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:

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:

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.

I to w zasadzie z grubsza cała teoria. Prawdziwe schody zaczynają się na zadaniach. Jak mi się bardzo zechce to podam rozwiązania. A może to wyglądać tak:

Przykładowe zadania

1. Ile różnych liczb trzycyfrowych podzielnych przez 5 można zapisać za pomocą cyfr : 1, 2, 3, 4, 5?
2. Na ile sposobów można ustawić na półce sześć książek tak , aby dwie wybrane książki stały obok siebie?
3. Ile różnych liczb trzycyfrowych można utworzyć z cyfr 0, 1, 3, 4, i 5 jeżeli założymy że cyfry w liczbie nie mogą się powtarzać?
4. Roztargniony Jasio zapomniał dwóch ostatnich cyfr numeru telefonu. Jaka jest maksymalna liczba prób, którą będzie musiał wykonać, aby trafić na właściwy numer?
5. W pudle jest 10 zielonych i 8 żółtych kul. Na ile sposobów możemy losowo wyjąć 5 kul, w tym:
   a) 3 kule zielone i 2 żółte
   b) 5 kul zielonych
   c) 5 kul jednego koloru
   d) co najmniej 4 kule żółte?
6. Na ile sposobów można wybrać sześć kart z talii 52 kart, w ten sposób, aby wśród wybranych kart znajdowały się dokładnie dwa piki?
7. Na ile różnych sposobów można ustawić w szeregu 5 lalek i 6 żołnierzyków, tak aby lalka nie sąsiadowała z lalką, a żołnierzyk z żołnierzykiem?
8. Do windy w 100 piętrowym wieżowcu wsiada 10 osób. Na ile sposobów mogą wysiąść na piętrach? (Sporo...)
9. Litery alfabetu Morse’a są utworzone z ciągu kropek i kresek, przy czym symbole mogą się powtarzać. Ile liter można utworzyć z czterech symboli?
10. Iloma sposobami można umieścić 20 koszul w trzech szufladach tak, aby w pierwszej było ich 10, w drugiej 6, a w trzeciej 4?

GÓRA         SZKOŁA