Kombinatoryka

Kombinatoryka stanowi dział matematyki, który zajmuje się obliczaniem liczby zbiorów, jakie można utworzyć w zadany sposób z elementów danego skończonego zbioru.

Dość często pojęcia permutacji, kombinacji, wariacji bez powtórzeń i wariacji z powtórzeniami są mylone ze sobą. W poniższej tabeli zestawione zostały podobieństwa i różnice między nimi. Tabela zawiera informacje, które ułatwią podjęcie decyzji, kiedy jaki wzór zastosować. Ponadto tablice te zawierają wszystkie podstawowe wzory z kombinatoryki.

Kombinatoryka - wzory

Niech:

\(p\) — oznacza permutację, kombinację lub wariację.
\(n\) — liczba elementów pewnego zbioru.
\(k\) — liczba elementów ciągu lub podzbioru dla tworzonych \(p\).

Tablica

nazwa p	Liczba p	Rodzaj	Czy kolejność wyrazów ma znaczenie?	Czy mogą występować powtórzenia tego samego elementu zbioru?
permutacje	\(P_n=n!\)	tworzymy ciągi \(n\)-elementowe	tak	nie
kombinacje	\(C^{k}_{n}={n \choose k}=\frac{n!}{k!(n-k)!}\)	tworzymy podzbiory \(k\)-elementowe	nie	nie
wariacje bez powtórzeń	\(V^{k}_{n}=\frac{n!}{(n-k)!}\)	tworzymy ciągi \(k\)-elementowe o różnych wyrazach	tak	nie
wariacje z powtórzeniami	\(W^{k}_{n}=n^k\)	tworzymy ciągi \(k\)-elementowe	tak	tak

Kombinatoryka — przykłady

A oto tabela z przykładami \(p\) utworzonymi z elementów zbioru trzyelementowego.

nazwa p	Określenie wszystkich \(p\) dla zbioru {a,b,c}
permutacje	(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)
kombinacje	1-elementowe: {a}, {b}, {c} 2-elementowe: {a, b}, {a, c}, {b, c} 3-elementowe: {a, b, c}
wariacje bez powtórzeń	1-elementowe: (a), (b), (c) 2-elementowe: (a, b), (a, c), (b, c), (b, a), (c, a), (c, b) 3-elementowe: (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)
wariacje z powtórzeniami	1-elementowe: (a), (b), (c) 2-elementowe: (a, b), (a, c), (b, c), (b, a), (c, a), (c, b), (a, a), (b, b), (c, c) 3-elementowe: (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a), (a, a, b), (a, a, c), (b, a, a), (c, a, a), (a, b, a), (a, c, a), (b, b, a), (b, b, c), (a, b, b), (c, b, b), (b, a, b), (b, c, b), (c, c, a), (c, c, b), (a, c, c), (b, c, c), (c, a, c), (c, b, c), (a, a, a), (b, b, b), (c, c, c)

Zastosowanie kombinatoryki do obliczania prawdopodobieństwa

Część zadań z rachunku prawdopodobieństwa da się sprowadzić do schematu polegającego na losowaniu \(k\) elementów z \(n\) elementów pewnego zbioru ze zwracaniem lub bez zwracania do zbioru. Takie podejście do zagadnienia pozwala korzystać z kombinatoryki podczas obliczania prawdopodobieństw.

Poniższa tabela podsumowuje wiedzę z zakresu kombinatoryki.

Oto kilka przykładów zadań z rachunku prawdopodobieństwa, w których zastosujemy elementy kombinatoryki.

Przykład 1

Obliczyć prawdopodobieństwo zdarzenia polegającego na wyrzuceniu w każdym rzucie kostką symetryczną inną liczbę oczek, w przypadku, gdy rzucamy kością 4 razy.

Zbiór zdarzeń elementarnych określamy następująco:

\(\Omega=\lbrace \omega = (k,l,m,n): k,l,m,n\in \lbrace 1,2,3,4,5,6 \rbrace \rbrace\)

Przykładowo zdarzeniem elementarnym będzie czwórka liczb \(1,4,5,3)\) lub \((6,6,6,6)\) itd. Jak obliczyć liczbę elementów zbioru zdarzeń elementarnych? Zauważ że losujemy kolejno cztery liczby ze zbioru sześciu liczb, przy czym kolejność losowania ma znaczenie, gdyż wynik \((1,2,3,4)\) jest wynikiem innym od \((4,3,2,1)\) — mamy tu dwa różne zdarzenia elementarne. Mamy losowanie ze zwracaniem, gdyż dla przykładu sześć oczek może wypaść kilka razy (czyli gdy wylosujemy sześć oczek, w kolejnym losowaniu znów można wylosować tę samą liczbę — trzeba ją więc po każdym losowaniu „zwrócić” do zbioru). Z powyższej tabeli wynika, że jeżeli mamy do czynienia z losowaniem ze zwracaniem, w którym kolejność elementów jest istotna, to do obliczenia liczby wszystkich możliwych wyników losowań w tym doświadczeniu stosujemy wariację z powtórzeniami.

Obliczamy więc 4-wyrazowe wariacje z powtórzeniami sześcioelementowego zbioru.

\(\overline{\overline{\Omega}} = W^4_6=6^4=1296\)

Zdarzenie \(A\) polega na wyrzuceniu w każdym rzucie innej liczby oczek, a więc to tak, jakby po wyrzuceniu na przykład szóstki nie zwrócić jej do zbioru i losować z pozostałych pięciu możliwych liczb. Kolejność oczywiście nadal ma znaczenie. Aby obliczyć liczbę wszystkich zdarzeń elementarnych sprzyjających zdarzeniu \(A\), skorzystamy z wariacji bez powtórzeń.

\(\overline{\overline{A}}=V^4_6=\frac{6!}{(6-4)!}=\frac{6!}{2!} = \frac{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6}{1\cdot 2} = 3\cdot 4\cdot 5\cdot 6=360\)

Obliczamy prawdopodobieństwo zdarzenia \(A\):

\(P(A)=\frac{\overline{\overline{A}}}{ \overline{ \overline{ \Omega}}} = \frac{360}{1296} = \frac{5}{18}\)

Przykład 2

W wytłaczance jest 9 jajek dobrych i 3 zepsute. Wyjęto 2 jajka. Jakie jest prawdopodobieństwo, że jajecznica z obu jajek będzie smaczna?

Zakładamy, że jajecznica jest smaczna, jeżeli powstała z dobrych jajek. Ponumerujemy jajka dobre od 1 do 9, a złe od 10 do 12. Nie ma znaczenia czy weźmiemy z wytłaczanki pierwsze a potem drugie jajko lub odwrotnie. Kolejność nie ma tu znaczenia. Jajek po wybraniu nie zwracamy do wytłaczanki, więc aby policzyć na ile sposobów możemy wylosować dwa jajka z 12 korzystamy z kombinacji dwuelementowych zbioru 12-elementowego.

\(\overline{\overline{\Omega}}=C^2_{12} = {12\choose 2}=\frac{12!}{2!(12-2)!} = \frac{12!}{2!10!}=\)

\(=\frac{10!\cdot 11\cdot 12}{2\cdot 10!}=\frac{11\cdot 12}{2}=66\)

Zdarzenie \(A\) oznacza wylosowanie 2 dobrych jajek, a więc losujemy dwa elementy ze zbioru dziewięcioelementowego (bo tyle jest dobrych jajek) i kolejność nie ma tu znaczenia, jajek nie zwracamy po losowaniu. Znów korzystamy z kombinacji.

\(\overline{\overline{A}}=C^2_9={9\choose 2}=\frac{9!}{2!(9-2)!}=\frac{9!}{2!7!} = \frac{7!\cdot 8\cdot 9}{2\cdot 7!}=\frac{72}{2}=36\)

Obliczamy prawdopodobieństwo zdarzenia \(A\):

\(P(A)=\frac{\overline{\overline{A}}}{ \overline{ \overline{\Omega}}} =\frac{36}{66}=\frac{6}{11}\)

Przykład 3

Jakie jest prawdopodobieństwo trafienia 6 w dużego lotka?

W dużym lotku losuje się bez zwracania 6 liczb z 49, kolejność nie ma znaczenia, więc zdarzeń elementarnych jest tyle ile kombinacji sześcioelementowych zbioru 49-elementowego:

\(\overline{\overline{\Omega}} = C^6_{49}={49\choose 6} = \frac{49!}{6!(49-6)!}=\frac{49!}{6!43!}=13983816\)

Zdarzenie \(A\) — wytypowanie 6-ciu liczb zachodzi w jednym przypadku.

\(\overline{\overline{A}}=1\)

Obliczamy prawdopodobieństwo zdarzenia \(A\):

\(P(A)=\frac{\overline{\overline{A}}}{ \overline{ \overline{\Omega}}} = \frac{1}{13983816}\)

Pytania

Co mają ze sobą wspólnego kombinatoryka i rachunek prawdopodobieństwa?

Otóż kombinatoryka dostarcza narzędzi do wyliczania prawdopodobieństwa pewnych zdarzeń, jeżeli tylko mamy do czynienia z losowaniem elementów z określonych zbiorów. Kombinatoryka daje pewne podstawy w rachunku prawdopodobieństwa.

Jakie ma zastosowanie kombinatoryka?

Kombinatoryka powstała w XVI wieku wraz z grami hazardowymi i w grach hazardowych ma praktyczne zastosowanie. Oprócz tego jest stosowana w informatyce, rachunku prawdopodobieństwa, w teorii liczb i teorii grafów.

Zadania z rozwiązaniami

Zadanie nr 1.

Ile słów czteroliterowych (niekoniecznie mających znaczenie) można utworzyć z 32 liter alfabetu, używając każdej z liter tylko raz?

Kombinatoryka

Kombinatoryka - wzory

Tablica

Kombinatoryka — przykłady

Zastosowanie kombinatoryki do obliczania prawdopodobieństwa

Przykład 1

Przykład 2

Przykład 3

Pytania

Co mają ze sobą wspólnego kombinatoryka i rachunek prawdopodobieństwa?

Zadania z rozwiązaniami

Inne zagadnienia z tej lekcji