3 Prawdopodobieństwo klasyczne
Przedyskutujemy klasyczny model prawdopodobieństwa, w którym każdy możliwy wynik naszego eksperymentu jest jednakowo prawdopodobny. Dzieje się tak kiedy rzucamy symetryczną monetą lub symetryczną kostką.
3.1 Model klasyczny
Na potrzeby tego rozdziału zakładać będziemy, że rozważana przestrzeń zdarzeń elementarnych \(\Omega\) jest skończona. Liczbę elementów zbioru \(A\) będziemy oznaczać przez \(|A|\). Spotyka się też oznaczenie \(\#A\). Dla liczby naturalnej \(n\) będziemy pisać \[\begin{equation*} [n] = \{ 1,2, \ldots, n\}. \end{equation*}\]
Jeżeli wszystkie zdarzenia elementarne są jednakowo prawdopodobne, to rozważana funkcja prawdopodobieństwa ma postać \[\begin{equation*} p(\omega) = \frac{1}{|\Omega|} \end{equation*}\] dla każdego \(\omega \in \Omega\). Stąd dla każdego zdarzenia \(A\subseteq\Omega\) mamy \[ \mathbb P[A]= \sum_{\omega \in A} \frac{1}{|\Omega|} = \frac{|A|}{|\Omega|}. \] Licznik jest liczbą wyników sprzyjających zdarzeniu \(A\), a mianownik liczbą wszystkich możliwych wyników. Jest to dokładnie definicja prawdopodobieństwa spotykana w szkole średniej.
Przykład 3.1 Rzucamy dwukrotnie symetryczną monetą. Wówczas każdy wynik jest jednakowo prawdopodobny. Przestrzenią wszystkich zdarzeń jest \[ \Omega=\{OO,OR,RO,RR\}, \] gdzie \(O\) oznacza orła, a \(R\) — reszkę. Każdy z czterech ciągów ma prawdopodobieństwo \(1/4\).
Zdarzeniu „wypadł dokładnie jeden orzeł” odpowiada zbiór \(\{OR,RO\}\), zatem jego prawdopodobieństwo wynosi \(2/4=1/2\).
Możemy też zapisać wynik doświadczenia jako liczbę orłów. Otrzymamy wtedy trzy możliwości: \(0\), \(1\) i \(2\). Nie są one jednak jednakowo prawdopodobne:
| # orłów | ciągi | \(\mathbb{P}\) |
|---|---|---|
| \(0\) | \(RR\) | \(1/4\) |
| \(1\) | \(OR,RO\) | \(1/2\) |
| \(2\) | \(OO\) | \(1/4\) |
Nie ma nic złego w opisywaniu doświadczenia za pomocą liczby orłów. Błędem byłoby dopiero przypisanie każdej z tych trzech wartości prawdopodobieństwa \(1/3\).
Zanim użyjesz modelu prawdopodobieństwa klasycznego, odpowiedz na dwa pytania:
- Co jest zdarzeniem elementarnym?
- Dlaczego wszystkie takie wyniki mają tę samą szansę?
To, że potrafimy wypisać kilka możliwości, nie oznacza jeszcze, że są jednakowo prawdopodobne.
Przykład 3.2 Rzucamy dwiema uczciwymi kostkami. Wynik zapisujemy jako parę \((i,j)\), gdzie \(i\) jest wynikiem pierwszej kostki, a \(j\) — drugiej. Wtedy \[ \Omega=[6]^2, \qquad |\Omega|=36. \] Suma \(7\) pojawia się dla sześciu par: \[ (1,6),\ (2,5),\ (3,4),\ (4,3),\ (5,2),\ (6,1). \] Jej prawdopodobieństwo wynosi więc \(6/36=1/6\). Suma \(2\) odpowiada tylko parze \((1,1)\), zatem ma prawdopodobieństwo \(1/36\). Możliwe sumy oczek również nie tworzą modelu klasycznego z jednakowymi wagami.
3.2 Zliczanie wyników
Przy analizie większych modeli często wypisywanie wszystkich elementów zbioru może okazać się zbyt uciążliwe. Okazuje się, że przy obliczaniu odpowiednich prawdopodobieństw nie jest to konieczne. Kluczowe jest wyznaczenie liczebności \(|A|\) interesującego nas zdarzenia \(A\). W tym celu bardzo pomocne są podstawowe schematy kombinatoryczne.
Przykład 3.3 Aby poznać liczebność zbioru nie musimy wypisywać wszystkich jego elementów.
Ile liczb całkowitych w zbiorze \([100]\) jest podzielnych przez \(3\)? Takich liczb jest \(\lfloor100/3\rfloor=33\).
Ile elementów \([100]\) nie jest podzielnych przez \(3\)? To proste: \(100-33=67\).
Ile elementów \(A\) jest podzielnych przez \(3\) lub przez \(5\), lub przez obie te liczby? Przez \(3\) podzielne są \(33\) elementy, a przez \(5\) podzielnych jest \(\lfloor100/5\rfloor=20\). Dodając te liczby, otrzymalibyśmy \(53\), czyli zbyt wiele: wielokrotności \(15\) zostałyby policzone dwukrotnie. Poprawna odpowiedź to \[ \left\lfloor\frac{100}{3}\right\rfloor+ \left\lfloor\frac{100}{5}\right\rfloor- \left\lfloor\frac{100}{15}\right\rfloor=47. \]
3.3 Reguła dodawania
Jeżeli obiekty, które chcemy policzyć, dzielą się na dwie rozłączne grupy \(A,B\subseteq \Omega\), to \[ |A \cup B| = |A| + |B|. \tag{3.1}\] Reguła ta mówi, że sumę rozłącznych zbiorów zliczamy, zliczając każdy zbiór osobno i dodając wyniki.
Przykład 3.4 Ze zbioru liczb \(\Omega = [30]\) losujemy jedną liczbę. Jakie jest prawdopodobieństwo, że będzie ona podzielna przez \(5\) lub przez \(7\)? Niech \(A\) będzie zdarzeniem, że wylosowana liczba jest podzielna przez \(5\). Wtedy \[\begin{equation*} A = \{5,10,15,20,25,30\}, \quad |A| = 6. \end{equation*}\] Dla zdarzenia \(B\), że wylosowana liczba jest podzielna przez \(7\), \[\begin{equation*} B = \{ 7, 14, 21 \}, \quad |B| = 3. \end{equation*}\] Skoro \(A\cap B =\emptyset\), \(|A \cup B | =9\) a co za tym idzie \[\begin{equation*} \mathbb{P}[A \cup B] = 3/10. \end{equation*}\]
Przykład 3.5 Rzucamy symetryczną kością dwudziestościenną. Wówczas przestrzenią zdarzeń elementarnych jest \[\begin{equation*} \Omega = [20]. \end{equation*}\] Jakie jest prawdopodobieństwo, że wylosowana liczba jest nieparzysta lub dzieli się przez \(4\)? Dla liczby \(p\) oznaczmy zdarzenie \[\begin{equation*} D_{p} = \{ n \in [20] \: | \: \mbox{$n$ dzieli się przez $p$} \} \subseteq \Omega. \end{equation*}\] Szukamy \(\mathbb{P}[N \cup D_4]\), gdzie \(N =\{1,3, \ldots, 19 \}\). Zauważmy, że zdarzenia \(N\) i \(D_4\) są rozłączne. Mamy \(\mathbb{P}[N]= 1/2\) i \(\mathbb{P}[D_4]= 1/4\). Stąd \[\begin{equation*} \mathbb{P}[N \cup D_4] = \mathbb{P}[N]+\mathbb{P}[D_4]= \frac{3}{4}. \end{equation*}\]
Podobnie jest dla rozłącznych zbiorów \(A_1\), \(A_2, \ldots, A_m\), \(m \in \mathbb{N}\), o liczebnościach \(n_1,\ldots,n_m\), to łącznie jest ich \[ \left| \bigcup_{j=1}^m A_j \right| = n_1+\cdots+n_m. \tag{3.2}\] Warunek rozłączności zapobiega wielokrotnemu zliczaniu tego samego obiektu.
Przykład 3.6 Ile liczb dwucyfrowych jest nieparzystych? Można policzyć parzyste i odjąć wynik od wszystkich liczb. Można również zastosować uogólnioną regułę Równanie 3.2. Niech \(S_k\) oznacza zbiór liczb dwucyfrowych o cyfrze jedności \(k\). Wówczas szukamy \[\begin{align*} & |S_1\cup S_3\cup S_5\cup S_7\cup S_9|\\ & =|S_1|+|S_3|+|S_5|+|S_7|+|S_9|. \end{align*}\] Każdy z tych zbiorów ma \(9\) elementów [dlaczego?], więc odpowiedź brzmi \(5\cdot9=45\).
Dla dowolnych skończonych zbiorów \(A\) i \(B\) mamy \[ |A\cup B|=|A|+|B|-|A\cap B|. \tag{3.3}\] Reguła Równanie 3.3 uwzględnia możliwość dwukrotnego policzenia części wspólnej \(A\cap B\). Można ją wyprowadzić z Równanie 3.1: zbiory \(A\) oraz \(B\setminus A\) są rozłączne, podobnie jak \(B\setminus A\) oraz \(A\cap B\). Zatem \[\begin{align*} |A\cup B| & = |A|+|B\setminus A|,\\ |B| & = |B\setminus A|+|A\cap B|. \end{align*}\] Stąd \[\begin{align*} |A\cup B|+|A\cap B| & =|A|+|B\setminus A|+|A\cap B| \\ & =|A|+|B|, \end{align*}\] co daje Równanie 3.3 . W terminach prawdopodobieństwa klasycznego zapisuje się to jako \[ \mathbb P[A\cup B] =\mathbb P[A]+\mathbb P[B]-\mathbb P[A\cap B]. \]
Przykład 3.7 Losujemy jedną z liczb \(1, 2, \ldots 1000\) w taki sposób, że wylosowanie każdej z nich jest jednakowo prawdopodobne. Wówczas przestrzenią zdarzeń elementarnych jest \[\begin{equation*} \Omega = \{ 1, 2, \ldots , 1000\}. \end{equation*}\] Jakie jest prawdopodobieństwo, że wylosowana liczba dzieli się przez \(3\) lub \(5\)? Dla liczby \(p\) oznaczmy zdarzenie \[\begin{equation*} D_{p} = \{ n \in \Omega \: | \: \mbox{$n$ dzieli się przez $p$} \}. \end{equation*}\] Szukamy \(\mathbb{P}[D_3\cup D_5]\). Zauważmy, że \[\begin{equation*} D_{3} = \{ 3m \: | \: 1\leq m \leq 333 \}, \end{equation*}\] więc \(\mathbb{P}[D_3] = \frac{333}{1000}\). Podobnie \(\mathbb{P}[D_5] =\frac{200}{1000}= \frac{1}{5}\). Skoro \(D_3 \cap D_5 = D_{15}\), to \(\mathbb{P}[D_3 \cap D_5] =\frac{66}{1000}= \frac{33}{500}\). Ostatecznie \[\begin{align*} \mathbb{P}[D_3 \cup D_5] & = \mathbb{P}[D_3]+\mathbb{P}[D_5]-\mathbb{P}[D_3\cap D_5] \\ & = \frac{467}{1000}. \end{align*}\]
Dla trzech zbiorów \(A\), \(B\), \(C\) mamy \[\begin{align*} |A \cup B \cup C| = & |A|+|B|+|C| \\ &-|A\cap B| - |B\cap C| \\& + |A\cap B \cap C|. \end{align*}\] Jest to przykład ogólnego schematu który przedyskutujemy na koniec tego rozdziału.
3.4 Reguła mnożenia
Dla skończonych zbiorów \(S_1, \ldots , S_k\), \[\begin{equation*} |S_1 \times \ldots \times S_k| = \prod_{j=1}^k|S_j|. \end{equation*}\] Jeżeli wszystkie \(S_i\) są tym samym zbiorem \(S\), otrzymujemy \(|S^k|=|S|^k\).
Będziemy często korzystać z reguły mnożenia, lecz niemal nigdy z formalnego zapisu sugerowanego w jej sformułowaniu. Chcemy przede wszystkim zachęcić do myślenia o problemach jako o procesach wieloetapowych. Pierwszy element możemy wybrać na \(|S_1|\) sposobów. Dla każdego takiego wyboru drugi możemy zrobić na \(|S_2|\) sposobów itd. Wyobrażenie sobie takiego procesu często pomaga znaleźć rozwiązanie.
Przykład 3.8 Liczba dróg od \(s\) do \(f\) na rysunku 2(a) wynosi \(3\cdot2\cdot2\cdot1=12\): pierwszą krawędź wybieramy na 3 sposoby, drugą i trzecią na 2 sposoby. Po wyborze pierwszych trzech krawędzi czwarta jest już wymuszona.
Podobne obliczenie zlicza drogi od \(s\) do \(f\) na rysunku 2(b). Można również zauważyć, że istnieje 12 dróg od \(s\) do \(v\) i 12 od \(v\) do \(f\), więc wszystkich dróg jest \(12\cdot12=144\).
Przykład 3.9 Niech \(S\) i \(T\) będą zbiorami skończonymi. Niech \[\begin{equation*} S^T = \{ f \: : \: f \colon T \to S\}. \end{equation*}\] Znajdziemy \(|S^T|\) liczbę różnych funkcji \(f \colon T \to S\). Będzie wygodnie przyjąć, że \[\begin{equation*} S = \{s_1, s_2, \ldots, s_n \}, \quad T = \{ t_1, \ldots, t_m\}, \end{equation*}\] gdzie \(|S| = n\) and \(|T|=m\). Dowolną funkcję \(f \colon T \to S\) można utożsamić jednoznacznie z \[ (f(t_1), f(t_2), \ldots , f(t_m)). \] Jest to element \(S^m\). Zatem z reguły iloczynu \[\begin{equation*} \left|S^T \right| = \left|S^m \right| = n^m. \end{equation*}\]
3.5 Wariacje
Definicja 3.1 \(k\)-wyrazową wariancją z powtórzeniami zbioru \(A\) nazywamy dowolną funkcję \(f \colon [k] \to A\).
Innymi słowy \(k\)-wyrazowa wariacja z powtórzeniami to po prostu ciąg długości \(k\) o wyrazach z \(A\). Zauważmy, że zbiorem wszystkich \(k\)-wyrazowych wariancji z powtórzeniami zbioru \(A\) jest \[\begin{equation*} A^k = A^{[k]} = \{ f \: | \: f \colon [k] \to A \}. \end{equation*}\]
Wniosek 3.1 Jeżeli \(|A| =n\), to dla każdego naturalnego \(k\) jest \[\begin{equation*} \left| A^{[k]} \right| = n^k \end{equation*}\] różnych wariacji z powtórzeniami zbioru \(A\).
Przykład 3.10 W dziesięciopiętrowym budynku windą jedzie siedem osób. Jakie jest prawdopodobieństwo, że wszystkie wysiądą na ostatnim piętrze? Jakie jest prawdopodobieństwo, że wszystkie wysiądą na tym samym piętrze? Zauważmy, że każdy scenariusz możemy zakodować w funkcji \(f \colon [7] \to [10]\). Tutaj \(j\)-tej osobie przyporządkowujemy jedno z dziesięciu pięter, na którym wysiada. W skutek czego wszystkich możliwości jest \(|[10]^7| = 10^7\). Zdarzenie, że wszyscy wysiądą na ostatnim piętrze, to \[\begin{equation*} \{(10, 10, \ldots, 10) \}. \end{equation*}\] Wobec czego jego prawdopodobieństwo wynosi \(10^{-7}\). Drugie zdarzenie, że wszyscy wysiądą na tym samym piętrze to \[\begin{equation*} \bigcup_{k=1}^{10} A_k, \end{equation*}\] gdzie \(A_k\) to zdarzenie, że wszyscy wysiądą na \(k\)tym piętrze. Dla \(k=10\) sprawdziliśmy już, że \(\mathbb{P}[A_{10}]=10^{-7}\). Nietrudno się przekonać, że dla dowolnego \(k \leq 10\), \(\mathbb{P}[A_k] =10^{-7}\). Skoro zdarzenia \(A_k\) są rozłączne, to nasze drugie zdarzenie ma prawdopodobieństwo \[\begin{equation*} \sum_{k=1}^{10} \mathbb{P}[A_k] = 10^{-6}. \end{equation*}\]
Definicja 3.2 \(k\)-wyrazową wariancją bez powtórzeń zbioru \(A\) nazywamy dowolną różnowartościową funkcję \(f \colon [k] \to A\). Zbiór wszystkich takich funkcji oznaczamy przez \[\begin{equation*} A^{\underline{k}} = \{ f \colon [k] \to A \: | \: f \mbox{ jest 1-1} \}. \end{equation*}\]
Dla naturalnych \(k, n\) przyjmujemy \[\begin{equation*} n^{\underline{k}} = n(n-1) \cdots (n-k+1). \end{equation*}\]
Jeżeli \(A\) ma \(n\) elementów, to pierwszy wyraz wariacji możemy wybrać na \(n\) sposobów, drugi na \(n-1\) sposobów, trzeci na \(n-2\) sposobów itd. Mamy więc \[\begin{equation*} |A^{\underline{k}}| = n(n-1) \cdots (n-k+1) = n^{\underline{k}}. \end{equation*}\] Wzór ten można całkowicie formalnie wyprowadzić z reguły mnożenia poprzez znalezienie bijekcji (jakiej?) między zbiorem \(A^{\underline{k}}\) a zbiorem \[\begin{equation*} [n]\times [n-1] \times \cdots \times [n-k+1]. \end{equation*}\]
Przykład 3.11 W dziesięciopiętrowym budynku windą jedzie siedem osób. Na ile sposobów mogą one wysiąść z windy, jeżeli każda osoba wysiada na innym piętrze? Zauważmy, że każdy scenariusz możemy zakodować w równowartościowej funkcji \(f \colon [7] \to [10]\), gdzie \(j\)-tej osobie przyporządkowujemy jedno z dziesięciu pięter, na którym wysiada. W skutek czego wszystkich możliwości jest \(|[10]^{\underline{7}}| = 10^{\underline{7}}\).
Przykład 3.12
Dla alfabetu \(\Sigma=\{a,b,c,d,e,f,g\}\) liczba słów długości \(5\) wynosi \(7^5=16\,807\), czyli \(|\Sigma^5|=16\,807\). Liczba słów bez powtarzających się liter to \(7\cdot6\cdot5\cdot4\cdot3=2520\): pierwszą literę wybieramy na \(7\) sposobów, drugą na \(6\) itd.
Dla \(\Sigma=\{a,b,c,d\}\) liczba słów długości \(2\) bez powtórzeń wynosi \(4\cdot3=12\). Można przedstawić te słowa za pomocą drzewa, jak na rysunku poniżej. Każda droga od początku odpowiada jednemu słowu bez powtórzeń; na przykład droga przez \(b\) do \(bc\) odpowiada słowu \(bc\). Podobne, lecz znacznie większe drzewo można wyobrazić sobie dla obliczenia z (a), a także dla dowolnej sytuacji, w której stosujemy regułę mnożenia.
Definicja 3.3 Permutacją zbioru \(A\) nazywamy dowolną bijekcję \(\sigma \colon A \to A\). Zbiór wszystkich permutacji oznaczamy przez \[\begin{equation*} A! = \{ \sigma \colon A \to A \: | \: \sigma \mbox{ jest 1-1 i na} \} \end{equation*}\]
Zauważmy, że permutacja zbioru o \(|A|=n\) elementach to \(n\) elementów wariacja zbioru \(A\). Wobec czego \[\begin{equation*} |A!| = n^{\underline{n}} = n(n-1) \cdots 2\cdot 1 = n! \end{equation*}\]
Przykład 3.13
Liczba uporządkowań talii \(52\) kart to \(52!\approx8{,}07\cdot10^{67}\).
Policzmy sposoby wybrania pięciu kart ze zwracaniem. Zliczamy uporządkowane piątki kart. Ze zwracaniem oznacza, że przed następnym losowaniem karta wraca do talii. Wyniki odpowiadają wzajemnie jednoznacznie elementom \(D^5\), gdzie \(D\) jest zbiorem \(52\) kart. Reguła mnożenia daje \(|D|^5=52^5\) możliwości.
Przy wyborze bez zwracania wylosowana karta nie wraca do talii. Nie wszystkie piątki z \(D^5\) są dopuszczalne: wykluczamy powtórzenia kart. Nadal stosujemy regułę mnożenia, otrzymując \(52\cdot51\cdot50\cdot49\cdot48=52^{\underline{5}}\) możliwości.
3.6 Kombinacje
Gdy kolejność jest istotna używamy wariacji. Często jednak kolejność nie ma znaczenia, a wtedy zamiast ciągów trzeba liczyć nieuporządkowane zbiory.
Definicja 3.4 \(k\)-wyrazową kombinacją bez powtórzeń zbioru \(A\) nazywamy dowolny \(k\)-elementowy zbiór \(B \subseteq A\). Zbiór wszystkich kombinacji bez powtórzeń oznaczamy przez \[\begin{equation*} {A \choose k} = \{ B \subseteq A \: | \: |B| = k \}. \end{equation*}\]
Wiemy już, że zbiór \(n\) elementów ma \(2^n\) podzbiorów. Dla \(0\le r\le n\) niech \(\binom nr\) oznacza liczbę jego podzbiorów \(r\)-elementowych. Jest to współczynnik dwumianowy, czytany „\(n\) po \(r\)”, zwany także liczbą kombinacji \(r\) elementów spośród \(n\). Oczywiście \[\begin{equation*} \left|{A \choose k}\right| = {|A| \choose k}. \end{equation*}\]
Przykład 3.14 Policzmy ciągi zer i jedynek długości \(72\) zawierające dokładnie \(17\) jedynek. Każdy taki ciąg wyznaczamy, wybierając \(17\) pozycji dla jedynek spośród \(72\) możliwych. Liczba ciągów wynosi więc \(\binom{72}{17}\). Ogólnie, liczba ciągów długości \(n\) zawierających \(r\) jedynek to \(\binom nr\). Aby zakończyć przykład, potrzebujemy wartości \(\binom{72}{17}\).
Twierdzenie 3.1 Dla \(0\le r\le n\) zachodzi \[ \binom nr = \frac{n^{\underline{r}}}{r!} = \frac{n!}{(n-r)!r!}. \]
Wybór \(r\)-elementowej wariacji zbioru \(n\)-elementowego można przeprowadzić w dwóch krokach: wybieramy podzbiór \(r\)-elementowy na \(\binom nr\) sposobów, następnie porządkujemy go na \(r!\) sposobów. Formalnie oznacza to, że istnieje bijekcja \[\begin{equation*} A^{\underline{r}} \to {A \choose r} \times [r]! \end{equation*}\] Reguła mnożenia daje \[ n^{\underline{r}}=\binom nr r! \]
Przykład 3.15 Rozważmy graf bez pętli, kompletny w tym sensie, że każdą parę różnych wierzchołków łączy dokładnie jedna krawędź. Ile ma krawędzi, jeśli ma \(n\ge2\) wierzchołków? Każda krawędź wyznacza dwuelementowy podzbiór zbioru wierzchołków \(V\) i odwrotnie. Zbiory te są w bijekcji, zatem liczba krawędzi wynosi \[ \binom n2=\frac{n!}{(n-2)!2!}=\frac{n(n-1)}2. \]
Twierdzenie 3.2 Dla dowolnych rzeczywistych \(x_0\) i \(x_1\) oraz naturalnego \(n\), \[\begin{equation*} (x_1+x_0)^n = \sum_{k=0}^n {n \choose k} x_1^k x_0^{n-k}. \end{equation*}\]
Poprzez wymnożenie wszystkich nawiasów \[\begin{equation*} (x_0+x_1)^n = \sum_{\epsilon \in \{ 0,1\}^n} x_{\epsilon(1)} \cdots x_{\epsilon(n)} \end{equation*}\] tutaj \(\epsilon = (\epsilon(1), \epsilon(2), \ldots , \epsilon(n))\) koduje który z \(x_0\) i \(x_1\) został wybrany do produktu. Dokładniej \(\epsilon(j)=1\) oznacza, że z \(j\)-tego nawiasu zostało wybrane \(x_1\) i \(\epsilon(j)=0\) oznacza, że zostało wybrane \(x_0\). Mamy \[\begin{equation*} \sum_{\epsilon \in \{ 0,1\}^n} x_{\epsilon(1)} \cdots x_{\epsilon(n)} = \sum_{k=0}^{n} |E_k| x_1^k x_0^{n-k}, \end{equation*}\] gdzie, \(E_k\) to zbiór tych \(\epsilon\), które wybierają dokładnie \(k\) razy \(x_1\) w trakcie wymnażania. Dokładniej \[\begin{equation*} E_k = \{ \epsilon \: : \: \epsilon(1)+\ldots +\epsilon(n) =k\}. \end{equation*}\] Pozostaje zauważyć, że \[\begin{equation*} |E_k| = {n \choose k}. \end{equation*}\]
3.7 Partia pokera
Dobrym sposobem ilustrowania tych technik jest zliczanie układów pokerowych. Talia składa się z czterech kolorów: trefli, kar, kierów i pików. Każdy kolor obejmuje \(13\) wartości: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K. A oznacza asa, J waleta, Q damę, a K króla. Każda wartość występuje cztery razy, po jednej karcie każdego koloru.
Ręka pokerowa jest zbiorem pięciu kart z talii 52 kart. Kolejność wyboru nie ma znaczenia. Strit składa się z pięciu kolejnych wartości, na przykład 8, 9, 10, J, Q. As może być na początku A, 2, 3, 4, 5 albo na końcu 10, J, Q, K, A. Klasyfikujemy ręce w następujące parami rozłączne grupy, wymienione od najmniej do najbardziej prawdopodobnych:
| Układ | Opis |
|---|---|
| Poker królewski | 10, J, Q, K, A w jednym kolorze. |
| Poker | Strit w jednym kolorze, który nie jest pokerem królewskim. |
| Kareta | Cztery karty tej samej wartości, na przykład cztery trójki i dziewiątka. |
| Ful | Trzy karty jednej wartości i dwie innej, na przykład trzy walety i dwie ósemki. |
| Kolor | Pięć kart jednego koloru, bez pokera i pokera królewskiego. |
| Strit | Strit, który nie jest pokerem ani pokerem królewskim. |
| Trójka | Trzy karty jednej wartości oraz dwie karty dwóch innych wartości. |
| Dwie pary | Dwie karty jednej wartości, dwie drugiej i piąta karta trzeciej wartości. |
| Jedna para | Dwie karty jednej wartości, jeśli ręka nie należy do żadnej wcześniejszej grupy; na przykład dwa króle, walet, dziewiątka i szóstka. |
| Brak układu | Żaden z powyższych układów. |
Przykład 3.16
- Wszystkich rąk pokerowych jest
\[\begin{align*} \binom{52}{5} & =\frac{52\cdot51\cdot50\cdot49\cdot48}{5\cdot4\cdot3\cdot2\cdot1} \\ & =52\cdot17\cdot10\cdot49\cdot6=2\,598\,960. \end{align*}\]
Ile jest fulów? Nazwijmy rękę z trzema waletami i dwiema ósemkami fulem typu \((J,8)\). Kolejność ma znaczenie: typ \((8,J)\) oznacza trzy ósemki i dwa walety. Typy \((J,J)\) i \((8,8)\) są niemożliwe. Typy fulów odpowiadają więc 2-permutacjom 13 wartości kart: jest ich \(13\cdot12\). Dla typu \((J,8)\) trzy walety wybieramy na \(\binom43=4\) sposoby, a dwie ósemki na \(\binom42=6\) sposobów. Mamy \(4\cdot6=24\) ręce tego typu. Rozumowanie działa dla każdego typu, więc wszystkich fulów jest \(13\cdot12\cdot24=3744\).
Ile rąk zawiera dwie pary? Typ \(\{Q,4\}\) oznacza dwie damy, dwie czwórki i kartę trzeciej wartości. Zapis zbiorowy podkreśla, że \(\{Q,4\}=\{4,Q\}\) i nie chcemy liczyć ręki dwukrotnie. Istnieje \(\binom{13}{2}\) typów. Dla każdego z nich obie pary wybieramy na \(\binom42\) sposobów każdą, a piątą kartę na \(52-8=44\) sposoby. Otrzymujemy
\[ \binom{13}{2}\binom42\binom42\cdot44=123\,552. \]
- Ile rąk jest stritami? Najpierw liczymy także pokery i pokery królewskie. Typ strita określa jego najwyższa wartość. Może nią być 5, 6, 7, 8, 9, 10, J, Q, K lub A, więc typów jest 10. Dla każdego typu mamy cztery możliwości dla każdej z pięciu kart: razem \(4^5\). Otrzymujemy \(10\cdot4^5=10\,240\) stritów. Odejmując 4 pokery królewskie i 36 pozostałych pokerów, dostajemy 10 200 zwykłych stritów.
3.8 Problem urodzin
Ile osób powinno znaleźć się w grupie, aby prawdopodobieństwo wspólnych urodzin przynajmniej dwóch z nich przekroczyło \(1/2\)?
Przyjmijmy uproszczony model: rok ma \(365\) dni, każda konfiguracja urodzin jest jednakowo prawdopodobna. Pomijamy więc lata przestępne i sezonowe różnice w częstości urodzeń.
Dla grupy \(k\) osób przestrzenią wyników jest
\[ \Omega=[365]^k. \]
Niech \(C_k\) oznacza zdarzenie, że co najmniej dwie osoby mają urodziny tego samego dnia. Bezpośrednie zliczanie wyników sprzyjających \(C_k\) jest niewygodne: wspólną datę może mieć jedna para, kilka par, trzy osoby, a nawet cała grupa.
Znacznie łatwiej policzyć zdarzenie przeciwne. Dla \(1\leq k\leq365\) wszystkie daty są różne z prawdopodobieństwem
\[ \mathbb P(C_k^c) =\frac{365^{\underline{k}}}{365^k} =\prod_{j=0}^{k-1}\left(1-\frac{j}{365}\right). \] Korzystając z nierówności \(1+x\leq e^x\) mamy \[\begin{equation*} \mathbb{P}[C_k^c] \leq e^{- \frac{1}{365}} e^{- \frac{2}{365}} \cdots e^{- \frac{k-1}{365}} = e^{- \frac{k(k-1)}{730}} \end{equation*}\] Na to aby \(\mathbb{P}[C_k^c]\leq 1/2\) wystarcza by \(k(k-1) \geq 730 \log(2) \approx 505,997\), czyli \(k \leq 23\).
Dla \(k\geq366\) mamy \(\mathbb P(C_k)=1\), ponieważ różne daty dla wszystkich osób są wtedy niemożliwe.
| Liczba osób \(k\) | Prawdopodobieństwo wspólnych urodzin |
|---|---|
| \(10\) | \(0{,}1169\) |
| \(20\) | \(0{,}4114\) |
| \(22\) | \(0{,}4757\) |
| \(23\) | \(0{,}5073\) |
| \(30\) | \(0{,}7063\) |
| \(40\) | \(0{,}8912\) |
| \(50\) | \(0{,}9704\) |
Prawdopodobieństwo rośnie wraz z liczbą osób. Porównanie wyników dla \(22\) i \(23\) osób pokazuje więc, że najmniejsza szukana liczba to \(23\).
Skąd tak niewielka liczba? Nie pytamy, czy ktoś ma urodziny w jednym z góry ustalonym dniu. Porównujemy wszystkie pary osób. W grupie \(23\) osób jest aż \[ \binom{23}{2}=253 \] pary. Jest więc wiele możliwości pojawienia się zgodności. Samej liczby par nie wolno jednak po prostu podzielić przez \(365\): zdarzenia zgodności poszczególnych par nie są rozłączne.
3.9 Zasada właczeń i wyłączeń
Zliczanie elementów części wspólnej zbiorów, gdzie kluczowym spójnikiem jest „i”, często jest łatwe. Natomiast bezpośrednie zliczanie elementów sumy zbiorów często sprawia trudność. Zasada włączeń i wyłączeń wyraża liczność sumy przez liczności odpowiednich części wspólnych.
Aby obliczyć liczność \(A_1\cup\cdots\cup A_n\), oblicz liczności wszystkich możliwych części wspólnych zbiorów z \(\{A_1,\ldots,A_n\}\). Dodaj wyniki dla części wspólnych nieparzystej liczby zbiorów, a odejmij wyniki dla części wspólnych parzystej liczby zbiorów.
Dla przykładu, dla dwóch zdarzeń \(A\), \(B\) mamy znany nam już wzór \[\begin{equation*} |A \cup B| = |A| + |B| - |A\cap B|. \end{equation*}\] Dla trzech zdarzeń \(A\), \(B\), \(C\), \[\begin{align*} & |A\cup B \cup C| = |A|+|B|+|C| \\ & -|A\cap B| - |A\cap C| - |B\cap C| \\ &+ |A\cap B \cap C|. \end{align*}\]
„Włączamy”, czyli dodajemy, liczności poszczególnych zbiorów; „wyłączamy”, czyli odejmujemy, części wspólne każdej pary; następnie dodajemy części wspólne każdej trójki itd.
Przykład 3.17
Policzmy liczby w \(S=\{1,2,\ldots,2000\}\) podzielne przez \(9\) lub \(11\). Dla dodatniego \(k\) niech \(D_k=\{n\in S:k\mid n\}\). Szukamy \(|D_9\cup D_{11}|\). Ponieważ \(|D_k|=\lfloor2000/k\rfloor\), mamy \(|D_9|=222\), \(|D_{11}|=181\) i \(|D_9\cap D_{11}|=|D_{99}|=20\). Zatem \(|D_9\cup D_{11}|=222+181-20=383\).
Przy podzielności przez \(9\), \(11\) lub \(13\) trudniejsze są tylko rachunki. Ponadto \(|D_{13}|=153\), \(|D_9\cap D_{13}|=|D_{117}|=17\), \(|D_{11}\cap D_{13}|=|D_{143}|=13\), \(|D_9\cap D_{11}\cap D_{13}|=|D_{1287}|=1\). Stąd \[\begin{align*} &|D_9\cup D_{11}\cup D_{13}|\\& =222+181+153-20-17-13+1\\ &=507. \end{align*}\]
Policzmy jeszcze liczby podzielne przez \(9\), \(11\), \(13\) lub \(15\). Trzeba uważać: na przykład \(D_9\cap D_{15}=D_{45}\), a nie \(D_{135}\), ponieważ podzielność przez \(9\) i \(15\) jest równoważna podzielności przez \(\operatorname{lcm}(9,15)=45\). Otrzymujemy \[\begin{align*} & |D_{15}|=133, \\ & |D_9\cap D_{15}|=|D_{45}|=44,\\ & |D_{11}\cap D_{15}|=|D_{165}|=12,\\ &|D_{13}\cap D_{15}|=|D_{195}|=10,\\ & |D_9\cap D_{11}\cap D_{15}|=|D_{495}|=4,\\ &|D_9\cap D_{13}\cap D_{15}|=|D_{585}|=3,\\ & |D_{11}\cap D_{13}\cap D_{15}|=|D_{2145}|=0,\\ &|D_9\cap D_{11}\cap D_{13}\cap D_{15}|=|D_{6435}|=0. \end{align*}\] Zasada włączeń i wyłączeń daje \[ \begin{align*} & |D_9\cup D_{11}\cup D_{13}\cup D_{15}| \\ &= 222+181+153+133\\ &-(20+17+44+13+12+10) \\ &+(1+4+3+0)-0=581. \end{align*} \]
Zasada przydaje się także do zliczania części wspólnej zbiorów, których dopełnienia są łatwiejsze do opisania.
Przykład 3.18 Losujemy liczbę z \(T=\{1000,1001,\ldots,9999\}\). Szukamy prawdopodobieństwa, że jej zapis zawiera co najmniej jedno \(0\), co najmniej jedną \(1\) i co najmniej jedną \(2\). Przykładami są \(1072\) i \(2101\). Łatwiej policzyć liczby, które nie zawierają określonych cyfr. Dla \(k=0,1,2\) niech \[ A_k=\{n\in T:\text{ zapis }n\text{ nie zawiera cyfry }k\}. \] Wtedy poszukiwany zbiór to \(A_0^c\cap A_1^c\cap A_2^c=(A_0\cup A_1\cup A_2)^c\), zgodnie z prawem de Morgana. Reguła mnożenia daje \(|A_1|=8\cdot9^3\): pierwsza cyfra nie może być zerem ani jedynką, a pozostałe nie mogą być jedynkami. Podobnie \[\begin{align*} |A_0|&=9^4=6561, \\ |A_1|&=|A_2|&=8\cdot9^3=5832,\\ |A_0\cap A_1|& =|A_0\cap A_2|=8^4=4096,\\ |A_1\cap A_2|&=7\cdot8^3=3584,\\ |A_0\cap A_1\cap A_2|&=7^4=2401. \end{align*}\] Stąd \[\begin{align*} |A_0\cup A_1\cup A_2| = & 6561+5832+5832\\ &-(4096+4096+3584)\\ & +2401=8850. \end{align*}\] Zdarzenie przeciwne ma \(9000-8850=150\) elementów, a jego prawdopodobieństwo wynosi \(150/9000=1/60\).
Przykład 3.19 Ustawiamy cyfry \(1,2,\ldots,9\) w losowej kolejności. Jakie jest prawdopodobieństwo, że żadna nie pozostanie na naturalnym miejscu, czyli \(1\) na pierwszym, \(2\) na drugim itd.? Łatwiej policzyć zdarzenie przeciwne. Niech \(A_k\) będzie zbiorem permutacji, w których na pozycji \(k\) stoi cyfra \(k\).
Każdy \(A_i\) ma \(8!\) elementów: ustalamy jedną cyfrę i dowolnie porządkujemy pozostałe. Każde \(A_i\cap A_j\), dla \(i<j\), ma \(7!\) elementów; każda część wspólna trzech takich zbiorów ma \(6!\) itd. Jest \(9\) zbiorów \(A_i\), \(\binom92\) par, \(\binom93\) trójek itd. Zatem \[\begin{align*} &|A_1\cup\cdots\cup A_9|\\ & =9\cdot8!-\binom92 7!+\binom93 6!-\binom94 5!\\ & +\ldots+\binom99 0! \end{align*}\] Ostatni składnik \(\binom99 0!=1\) zlicza permutację identycznościową, w której żadna cyfra się nie przesunęła. Ponieważ \(\binom9m(9-m)!=9!/m!\), dostajemy \[\begin{align*} & |A_1\cup\cdots\cup A_9|\\ & =9!\left(\frac1{1!}-\frac1{2!}+\frac1{3!}-\cdots-\frac1{8!}+\frac1{9!}\right). \end{align*}\] Wszystkich permutacji jest \(9!\), więc prawdopodobieństwo co najmniej jednej cyfry na swoim miejscu to \[ 1-1/2!+1/3!-\cdots-1/8!+1/9!. \] Prawdopodobieństwo, że żadna nie jest na swoim miejscu, wynosi \[\begin{align*} & \frac1{2!}-\frac1{3!}+\cdots+\frac1{8!}-\frac1{9!}\\ & =1-1+\frac1{2!}-\frac1{3!}+\cdots+\frac1{8!}-\frac1{9!}. \end{align*}\]
To początek szeregu dla \(e^{-1}\), gdzie \(e\approx2{,}71828\). Odpowiedź wynosi zatem około \(1/e\approx0{,}368\).
Twierdzenie 3.3 Dla dowolnych skończonych podzbiorów \(A_1, \ldots , A_n \subseteq \Omega\), \[\begin{align*} & \left| A_1 \cup A_2 \cup \ldots \cup A_n \right| = \sum_{k=1}^m |A_k| \\ &- \sum_{k,j=1, k<j}^n |A_k\cap A_j| + \ldots (-1)^{n-1}|A_1\cap \ldots A_n| \end{align*}\]
Twierdzenie o dwumianie daje wzór: \[\begin{align*} & 0=\sum_{k=0}^m(-1)^k\binom mk \\ & =1-\binom m1+\binom m2-\cdots+(-1)^m. \end{align*}\] Dla nieparzystego \(m\) łatwo dostrzec, że składniki \(\binom mk\) i \(\binom m{m-k}\) mają przeciwne znaki i się redukują. Dla parzystego \(m\) nie jest to tak oczywiste bez twierdzenia.
Wzór ten daje dowód zasady włączeń i wyłączeń. Rozważmy element należący do dokładnie \(m\) zbiorów, powiedzmy \(A_1,\ldots,A_m\). W sumie liczności zbiorów zliczamy go \(m\) razy, następnie odejmujemy po jednym razie dla każdej pary, dodajemy dla każdej trójki itd. Jego łączny wkład wynosi \[ \binom m1-\binom m2+\cdots+(-1)^{m+1}\binom mm=1. \] Każdy element sumy został więc policzony dokładnie raz.