Rachunek prawdopodobieństwa – elementy kombinatoryki
Początki rachunku prawdopodobieństwa związane są z grami losowymi, do których należy na przykład gra w kości, i chęcią poznania szansy wygranej.
Przykład 1:
Weźmy pod uwagę sytuację, gdy rzucamy dwiema monetami, np. dwuzłotówką i pięciozłotówką. Chcemy znać ilość możliwych wyników tego doświadczenia.
Niech „o” oznacza otrzymanie orła, a „r” - reszki na monecie dwuzłotowej, natomiast „O” – orła, a „R” – reszki na monecie pięciozłotowej.
Mamy 4 możliwe wyniki doświadczenia: oO, Or, rO, rR.
Aby obliczyć ilość wyników doświadczenia w powyższej sytuacji można skorzystać z twierdzenia.
Twierdzenie (Reguła mnożenia):
Jeżeli zbiór A ma m elementów, a zbiór B ma n elementów, to liczba różnych par (x,y) takich, że xϵA oraz yϵB jest równa m∙n.
W przykładzie 1 zbiór A składa się z elementów „o” i „r”, natomiast zbiór B z elementów „O” i „R”. Ilość elementów w każdym ze zbiorów wynosi 2, więc ilość możliwych wyników wynosi 2∙2=4.
Przykład 2:
Na ile sposobów możemy ustawić na półce trzy książki w różnej kolejności?
Oznaczmy te książki kolejno literami a, b, c i wypiszmy wszystkie możliwości:
abc acb bac bca cab cba
Czyli książki te możemy ustawić na 6 sposobów. Warto zauważyć, że w każdej z możliwości, każdej z książek użyliśmy tylko raz.
W tym przykładzie podaliśmy wszystkie trzywyrazowe ciągi, jakie można utworzyć, przestawiając litery a,b,c. Takie ciągi nazywamy permutacjami.
Definicja 1:
Permutacją n-elementowego zbioru A nazywamy każdy n-wyrazowy ciąg utworzony ze wszystkich elementów tego zbioru.
Twierdzenie:
Wszystkich permutacji zbioru n-elementowego jest n! (czytaj: n silnia).
Definicja 2:
Dla n>1 sumbol n! oznacza iloczyn kolejnych liczb naturalnych od 1 do n:
n!=1 • 2 • 3 • ... • n.
Przyjmujemy również, że 0!=1 i 1!=1.
W przykładzie 2 ilość możliwości możemy policzyć w następujący sposób:
3!=1∙2∙3=6
(Jest tak, ponieważ nasz zbiór składa się z trzech elementów, czyli trzech książek)
Przykład 3:
Pewien kod tworzymy z trzech liter wybranych spośród następujących: A, B, C, D, E, F, G, H, przy czym litery nie mogą się powtarzać. Ile jest takich kodów?
Na pierwszym miejscu możemy wpisać jedną z ośmiu liter, na drugim jedną z siedmiu (ponieważ jedna już została wykorzystana do uzupełnienia pierwszego miejsca), a na trzecim – jedną z pozostałych liter, czyli jedną z sześciu.
Zatem jest 8 ∙ 7 ∙ 6 = 336 kodów.
Opisane powyżej kody to przykłady wariacji bez powtórzeń.
Definicja 3:
Każdy k-wyrazowy ciąg utworzony z różnych elementów n-elementowego zbioru A, gdzie k≤n, nazywamy k-elementową wariacją bez powtórzeń elementów zbioru A (wariacją bez powtórzeń zbioru A).
Twierdzenie:
Jeśli k≤n, to wszystkich k-elementowych wariacji bez powtórzeń zbioru n-elementowego jest:
$\text{n\ } \bullet \ (n\ - \ 1)\ \bullet \ ...\ \bullet \ (n\ \ k\ + \ 1)\ = \ \frac{n!}{\left( n - k \right)!}$ .
W przykładzie 3 ilość kodów możemy obliczyć używając wzoru z powyższego twierdzenia. W tym przypadku n wynosi 8 (bo tytle jest liter od A do H), a k wynosi 3 (bo tyle liter wybieramy do utworzenia kodu). Zatem ilość kodów wynosi:
$$\frac{8!}{\left( 8 - 3 \right)!} = \frac{8!}{5!} = \frac{1 \bullet 2 \bullet 3 \bullet 4 \bullet 5 \bullet 6 \bullet 7 \bullet 8}{1 \bullet 2 \bullet 3 \bullet 4 \bullet 5} = 6 \bullet 7 \bullet 8 = 336\ .$$
Przykład 4:
Ile jest wszystkich liczb trzycyfrowych, w których zapisie mogą występować tylko cyfry 1 i 2?
Wypiszmy wszystkie możliwości:
111 121 211 221
112 122 212 222
Zatem tych liczb jest 8.
Każdą z trzech cyfr możemy wybrać na dwa sposoby, zatem jest ich 2 ∙ 2 ∙ 2 = 8.
Definicja 4:
Każdy k-wyrazowy ciąg, w którym wyrazy mogą się powtarzać, utworzony z elementów zbioru A, nazywamy k-elementową wariacją z powtórzeniami elementów zbioru A (wariacją z powtórzeniami zbioru A).
Twierdzenie:
Wszystkich k-elementowych wariacji z powtórzeniami zbioru n-elementowego jestnk .
W przykładzie 4 za n przyjmujemy 2 (bo mamy do wyboru tylko cyfry 1 i 2), a za k przyjmujemy 3 (bo chcemy stworzyć ciąg 3-cyfrowy).
Zatem szukanych liczb trzycyfrowych jest: 23 = 2 • 2 • 2 = 8 .
Przykład 5:
W turnieju szachowym brało udział pięcioro zawodników. Ile partii rozegrano, jeśli każdy uczestnik rozegrał jedną partię z każdym z pozostałych?
Oznaczmy uczestników numerami 1, 2, 3, 4, 5. Wypiszmy wszystkie możliwości rozegranych partii biorąc pod uwagę, że zawodnik nie może grać ze sobą samym oraz że na przykład para uczestników {1,2} oznacza tą samą parę, co {2,1}.
Mamy zatem następujące partie:
{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}. Jest ich 10.
Każdy z powyższych podzbiorów nazywamy dwuelementową kombinacją zbioru pięcioelementowego.
Definicja 5:
Każdy k-elementowy podzbiór zbioru n-elementowego A (n ≥ k) nazywamy k-elementową kombinacją tego zbioru.
$$\frac{n!}{k!\left( n - k \right)!}\text{\ .}$$
$$\frac{5!}{2!\left( 5 - 2 \right)!} = \frac{5!}{2! \bullet 3!} = \frac{1 \bullet 2 \bullet 3 \bullet 4 \bullet 5}{1 \bullet 2 \bullet 1 \bullet 2 \bullet 3} = \frac{4 \bullet 5}{1 \bullet 2} = \frac{20}{2} = 10\ .$$