Część 2: Anomalie i paradoksy

Permutacje, czyli karty w tas

Na ile sposobów można ułożyć w ciąg n różnych elementów? Na pewno było o tym w szkole, ale nie zawadzi odświeżyć sobie pamięć i na rozgrzewkę pogimnastykować mózg. Zaczynamy od pierwszej pozycji ciągu: ponieważ może ją zająć dowolny element, mamy n możliwości jej zapełnienia. Przechodzimy do pozycji drugiej. Jeden element już wykorzystaliśmy, więc liczba możliwych wyborów w tym przypadku jest mniejsza: n–1. Dla trzeciej pozycji będzie ich n–2 i tak dalej. Kiedy zapełnimy już wszystkie pozycje oprócz dwóch, zostają nam dwa elementy, czyli dwie możliwości wyboru dla przedostatniej pozycji. Tu kończy się wybór, bo ostatni element musi zająć ostatnie wolne miejsce.

Liczbę wszystkich możliwych ciągów złożonych z tych samych elementów, ale różniących się kolejnością (zwanych permutacjami)¹ otrzymujemy, mnożąc liczby wyborów dla każdej pozycji:

n · (n–1) · (n–2) · … · 2 · 1,

albo (odwracając kolejność mnożenia):

1 · 2 · 3 · … · (n–1) · n.

Jest to zatem iloczyn wszystkich liczb od 1 do n. Nazywany go silnią i oznaczamy skrótowo tak:²

n!

Ponieważ zero elementów można ułożyć tylko na jeden sposób (jako ciąg pusty), przyjmujemy dodatkowo, że 0! = 1. Zauważmy, że dla każdej dodatniej liczby całkowitej n! = (n–1)! · n.

Wartość silni rośnie bardzo szybko wraz ze wzrostem n. Pięć elementów można ułożyć na 1 · 2 · 3 · 4 · 5 = 120 różnych sposobów, ale liczba permutacji dziesięciu elementów wynosi już 10! = 3 628 800 (ponad trzy i pół miliona). Tasując talię zawierającą 52 karty, otrzymujemy jedną z około 80 undecylionów, czyli 80 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 możliwych permutacji.³ Jest to kilkakrotnie więcej niż szacowana liczba atomów w naszej Galaktyce (Drodze Mlecznej). Dużo, ale przyzwyczajajmy się do dużych liczb.

Najważniejsze pytanie kombinatoryki

Zastanówmy się teraz, na ile różnych sposobów można wybrać k elementów ze zbioru n-elementowego. Oznaczmy tę liczbę jako C(n, k). Jest to tak zwana liczba kombinacji bez powtórzeń z n elementów po k, a skrótowo „n po k” lub „n nad k”. Zwróćmy uwagę, że wybór k elementów jest równoważny podzieleniu zbioru na dwa podzbiory zawierające odpowiednio k i n–k elementów. Pierwszy z nich można ułożyć w ciąg na k! sposobów, a drugi na (n–k)! sposobów. Oba ciągi można ustawić obok siebie i połączyć w jeden, złożony z n elementów. Dla każdego spośród takich podziałów – a jest ich łącznie C(n, k) – istnieje k!(n–k)! połączonych ciągów n-elementowych. Ile jest ich w sumie dla wszystkich możliwych podziałów na k i n–k elementów? Oczywiście tyle samo, co wszystkich permutacji n elementów, bo każda taka permutacja odpowiada unikatowemu połączeniu pewnej pary permutacji k elementów wybranych i n–k pozostałych. Stąd wynika, że

C(n, k) · k!(n – k)! = n!

I oto już wiemy, jak obliczyć liczbę możliwych wyborów k spośród n elementów:

C(n, k) = n!/k!(n – k)!

Żeby nie mnożyć nawiasów ponad potrzebę, przyjmijmy konwencję, że najpierw wykonujemy mnożenie zapisane bez znaku działania, czyli n!(n–k)!, a dopiero potem dzielenie zapisane przy użyciu ukośnika.⁴

Notacja C(n, k) jest trochę toporna w porównaniu z powszechnie używanym profesjonalnym zapisem „n nad k”:

Zapis ten zwany jest po polsku symbolem Newtona, choć wprowadził go Andreas von Ettingshausen w 1826 r. (99 lat po śmierci sir Isaaca). Będziemy jednak chwilami używać zamiennie także mniej eleganckiej notacji C(n, k) zwłaszcza wówczas, gdy trzeba zapisać wyrażenie matematyczne w jednej linii tekstu.

Co wykombinował Pascal

Liczbę kombinacji z n po k potrafił obliczyć już sławny matematyk indyjski z XII w., Bhāskara II. Natomiast w połowie XVII w. Blaise Pascal poświęcił liczbom C(n, k) rozprawę, pokazując, że układają się one w piękny schemat zwany odtąd trójkątem Pascala. Wygląda on tak:

Wzdłuż dwóch boków trójkąta widnieją same jedynki, a każda liczba wewnątrz trójkąta jest sumą dwóch liczb położonych tuż nad nią (na lewo i na prawo) w poprzednim rzędzie. Rząd oznaczony numerem n zawiera liczby C(n, 0), C(n, 1), C(n, 2) itd. aż do C(n, n–1), C(n, n). Łatwo policzyć, że jest ich łącznie n+1.

Sprawdźmy, czy to działa. Na ile sposobów można wybrać trzy elementy spośród ośmiu?

C(8, 3) = 8!/(3! · 5!)
= 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8/(1 · 2 · 3)(1 · 2 · 3 · 4 · 5)
= 6 · 7 · 8/(2 · 3)
= 7 · 8
= 56.

Jak to w matematyce – wszystko się zgadza: na czwartej pozycji w rzędzie nr 8, odpowiadającej C(8, 3), odnajdujemy liczbę 56.

Trójkąt Pascala można łatwo rozbudowywać, dodając kolejne, coraz dłuższe rzędy. Zarówno sam trójkąt, jak i liczby C(n, k) mają wiele ciekawych właściwości, z których szczególnie ważna jest następująca: wyrażenie a + b podniesione do potęgi n można zapisać w postaci następującej sumy (pamiętając, że a⁰ = 1, a a¹ = a):

Jest to niezwykle użyteczny w zastosowaniach rachunkowych wzór dwumianowy Newtona; liczby C(n, k) nazywane są współczynnikami dwumianowymi. Na pewno każdy pamięta następujący prosty przypadek (dla n = 2):

(a + b)² = a² + 2ab + b²,

ale korzystając z kolejnych rzędów trójkąta Pascala, otrzymujemy także na przykład (dla n = 8):

(a + b)⁸ = a⁸ + 8a⁷b + 28a⁶b² + 56a⁵b³ + 70a⁴b⁴
+ 56a³b⁵ + 28a²b⁶ + 8ab⁷ + b⁸.

Na pewno zauważyliście, że trójkąt Pascala jest symetryczny. Każdy rząd czytany od końca wygląda tak samo jak czytany od początku. Nie ma w tym nic dziwnego, bo jak łatwo sprawdzić, C(n, k) = C(n, n–k). Przecież wybór k elementów spośród n jest równoważny wyborowi n–k elementów „do odrzucenia”. Liczba kombinacji z 8 elementów po 3 jest zatem dokładnie taka sama jak liczba kombinacji z 8 elementów po 5.

Szansa na milion

Uzbrojeni w znajomość permutacji, silni i kombinacji bez powtórzeń możemy teraz zaatakować następujący problem: na ile sposobów można wybrać sześć różnych elementów ze zbioru 49-elementowego? Trudno byłoby rozpisywać trójkąt Pascala aż do rzędu nr 49 (potrzebna byłaby duża kartka papieru i trochę czasu poświęconego na dodawanie coraz dłuższych liczb), ale możemy skorzystać wprost ze znanego już wzoru:

C(49, 6) = 49!/(6! · 43!)

Zauważmy, że 49! = 43! · 44 · 45 · 46 · 47 · 48 · 49, możemy więc uprościć licznik i mianownik ułamka, dzieląc oba z nich przez 43!:

C(49, 6) = 44 · 45 · 46 · 47 · 48 · 49/6!
= 44 · 45 · 46 · 47 · 48 · 49/(1 · 2 · 3 · 4 · 5 · 6).

Kontynuując upraszczanie, dopóki nie pozbędziemy się wszystkich liczb w mianowniku, dostajemy w końcu:

C(49, 6) = 44 · 3 · 46 · 47 · 49 = 13 983 816.

Taka jest właśnie liczba kombinacji bez powtórzeń sześciu elementów wybieranych spośród czterdziestu dziewięciu. Czy te liczby brzmią znajomo? Tak jest! – mówimy o liczbie możliwych wyników losowania Lotto lub Lotto Plus (zasady obu są takie same). Zakładając, że maszyna losująca jest neutralna, czyli każdy wynik jest jednakowo prawdopodobny, stwierdzamy, że szansa na szczęśliwe wylosowanie zwycięskiej szóstki wynosi 1/13 983 816 czyli 0,0000000715…

Kilka założeń upraszczających

Tu dokonamy drobnego zaokrąglenia: z dokładnością do promila prawdopodobieństwo trafienia szóstki w Lotto wynosi jeden do czternastu milionów. Na ogół uważamy, że prawdopodobieństwo tego rzędu oznacza coś niemożliwego; niemniej jednak ktoś przecież od czasu do czasu trafia szóstkę. Rzecz w tym, że nawet zjawiska bardzo mało prawdopodobne zdarzają się regularnie przy odpowiednio dużej liczbie prób. Jeśli organizator Lotto sprzeda odpowiednio wielką liczbę kuponów, to szansa, że co najmniej jeden z nich okaże się zwycięski, staje się całkiem realna (jak niebawem się przekonamy).

Co tam zresztą Lotto! Fizycy badający zderzenia protonów o wielkiej energii poszukują oddziaływań zachodzących z prawdopodobieństwem rzędu jeden do stu bilionów (na przykład jednoczesnego wygenerowania trzech ciężkich bozonów cechowania, WWW lub WWZ). I nie chodzi tylko o to, żeby taki proces uchwycić raz, ale żeby obserwacje powtórzyły się, zapewniając wysoki poziom istotności statystycznej wyników (co praktycznie wyklucza błąd pomiaru lub interpretacji danych). Właśnie dlatego w Wielkim Zderzaczu Hadronów (LHC) detektory poszukują takich ultrarzadkich (prawie niemożliwych) zjawisk wśród biliardów rejestrowanych zderzeń.

Liczba grających w Lotto i Lotto Plus waha się w szerokich granicach, ale ponieważ nie chodzi nam tu o realistyczne modelowanie prawdziwej gry, tylko o zilustrowanie jej podstaw matematycznych, poczynimy kolejne założenie upraszczające. Przyjmijmy, że w pojedynczym losowaniu bierze udział średnio 1,4 mln zakładów. Tygodniowo odbywa się po sześć losowań. Rocznie jest ich zatem nieco ponad trzysta, czyli grający podejmują ok. 420 mln prób trafienia szóstki. Jeżeli prawdopodobieństwo wygranej wynosi 1/14 000 000, to można się spodziewać przeciętnie 30 takich trafień rocznie. Zgadza się to w granicach rozsądku ze stanem faktycznym.

Wypełnianie kuponów, czyli próby Bernoulliego

Czym jest Lotto (Plus) z matematycznego punktu widzenia? Czymś, co nazywamy uczenie procesem Bernoulliego, czyli ciągiem niezależnych prób Bernoulliego – eksperymentów losowych, w których prawdopodobieństwo sukcesu jest stałe i wynosi p ≈ 1/14 000 000, a prawdopodobieństwo niepowodzenia q = 1 – p ≈ 13 999 999/14 000 000 = 0,99999992857…⁵ Pojedyncze losowanie to ok. 1 400 000 takich prób. Oznaczmy tę liczbę symbolem N. W naszym przykładzie tak się składa, że p = 0,1/N, a q = 1 – 0,1/N.

Jakie jest prawdopodobieństwo, że nikt nie trafi szóstki? Ponieważ próby są niezależne, wystarczy przemnożyć przez siebie prawdopodobieństwa porażki dla każdej z nich. Wychodzi (1 – 0,1/N)^N. Oznaczmy sobie tę wartość symbolem P(0|N), czyli prawdopodobieństwo 0 sukcesów w N próbach.

Tak się składa, że kiedy n dąży do nieskończoności, to wartość wyrażenia (1 + 1/n)ⁿ dąży do liczby e, czyli sławnej stałej Eulera. Zapisujemy to tak:

lim_{n → ∞} (1 + 1/n)ⁿ = e = 2,71828…

Jest to liczba niewymierna, jedna z najważniejszych stałych w całej matematyce. Oprócz zera i jedności tylko liczba π może się z nią od biedy równać. Wyskakuje ona jak diabełek z pudełka w tak wielu sytuacjach, że nie powinniśmy się dziwić jej pojawieniu się także tutaj. Dla dowolnej liczby rzeczywistej x prawdziwa jest również następująca tożsamość:

lim_{n → ∞} (1 + x/n)ⁿ = e^x.

Dla dużych wartości n wyrażenie (1 + x/n)ⁿ jest niemal dokładnie równe e^x, a zgodzimy się chyba, że N = 1 400 000 to liczba duża (choć jak każdej liczbie, daleko jej do prawdziwej nieskończoności). W rozważanym tu przypadku x = –0,1, a zatem prawdopodobieństwo, że w danym losowaniu nikt nie trafi szóstki, wynosi z bardzo dobrą dokładnością e^−0,1. Sięgamy po kalkulator i przekonujemy się, że P(0|N) ≈ e^−0,1 = 0,904837…

A jakie jest prawdopodobieństwo, że wypadnie dokładnie jedna szóstka? Spójrzmy na cały ciąg prób składających się na jedno losowanie. Jest ich N. Zwycięski zakład można zatem wybrać na N sposobów. Prawdopodobieństwo sukcesu wybranego zakładu wynosi p = 0,1/N, a prawdopodobieństwo jednoczesnej porażki wszyskich N – 1 pozostałych wynosi q^N–1 = (1 – 0,1/N)^N–1. Możemy więc obliczyć prawdopodobieństwo wystąpienia dokładnie 1 sukcesu w N próbach:

Dla wielkich liczb N i N–1 to „prawie tyle samo”, a więc możemy przyjąć, że P(1|N) ≈ 0,1 e^–0,1 = 0,090483… (z dokładnością do szóstego miejsca po przecinku). Warto zwrócić uwagę, że P(0|N) + P(1|N) = 0,995321…, czyli oba prawdopodobieństwa nie sumują się do jedności. Pozostaje niewielka reszta wynosząca 0,004678… ≈ 1/214.

Co to oznacza? Ano, to, że w pojedynczym losowaniu z prawdopodobieństwem ok. 90,5% żaden gracz nie wygra głównej nagrody. Z prawdopodobieństwem ok. 9% zwycięzca będzie dokładnie jeden. Z prawdopodobieństwem ok. 0,5% zdarzą się co najmniej dwa trafienia szóstki. To niby niedużo, ale jeśli rocznie odbywa się ponad 300 losowań, to można oczekiwać, że średnio jeden lub dwa razy w roku w jednym losowaniu wygrają dwa zakłady lub większa ich liczba.

Gramy dalej

Jak obliczyć ogólnie P(k|n), czyli prawdopodobieństwo uzyskania dokładnie k sukcesów w n próbach Bernoulliego? Jeśli się zastanowić, to nie jest to wcale trudne. Dla każdej pojedynczej kombinacji k elementów wybranych spośród n prawdopodobieństwo niezależnego wystąpienia k sukcesów i n–k porażek (o prawdopodobieństwach odpowiednio p i q) jest następującym iloczynem:

p^kq^n–k = p^k(1 – p)^n–k.

Takich cząstkowych prawdopodobieństw trzeba zsumować tyle, ile jest kombinacji z n po k, czyli C(n, k). Ostatecznie zatem:

Dla k = 0 mamy C(n, 0) = 1 (dla dowolnego n, patrz trójkąt Pascala), stąd P(0|n) = (1 – p)ⁿ. Dla k = 1 mamy C(n, 1) = n!/(n -1)! = n, dlatego P(1|n) = np(1 – p)^n–1. Oba wzory właściwie już wyprowadziliśmy powyżej innym sposobem.

A ile wynosi P(2|N), czyli prawdopodobieństwo dwóch trafień szóstki w jednym losowaniu?

C(n, 2) = n!/2!(n–2)! = (n–1)n/2,

a zatem:

W naszym przykładzie p = 0,1/N, czyli p² = 0,01/N²; zauważmy ponadto, że wyrażenie (1 – 0,1/N)^N–2 dla bardzo dużego N nadal wynosi z dużą dokładnością e^−0,1 = 0,904837… Uwzględniwszy to wszystko, otrzymamy następującą wartość:

Mówiąc po ludzku, przy przyjętych przez nas założeniach średnio raz na 221 losowań (to jest przynajmniej raz w roku) można się spodziewać dwu głównych wygranych w jednym losowaniu. Suma P(0|N) + P(1|N) + P(2|N) wynosi 0,999845…, czyli nadal jest różna od 1. Pozostaje reszta równa 0,00015465… ≈ 1/6466. Oznacza ona prawdopodobieństwo, że jednocześnie padną co najmniej trzy główne wygrane. Przy naszych założeniach można oczekiwać takiego cudu raz na ok. 20 lat.

Chyba wystarczy tych rachunków jak na jeden wpis. W drugiej części miniserii sprawdzimy, jak zmieniają się szanse trafienia jednej, dwóch lub większej liczby szóstek w zależności od liczby grających. Zastanowimy się także, co sądzić o przypadkach, gdy podejrzanie duża liczba graczy jednocześnie trafia zwycięską kombinację. Czy oznacza to, że ktoś gdzieś dopuścił się nieuczciwości? A może matematyka jest do kitu? Cóż, zobaczymy.

Przypisy

1. Permutacją nazywamy zarówno operację polegającą na zmianie kolejności elementów uporządkowanych w ciąg, jak i dowolny wynik takiej operacji. ↩︎
2. Czytaj: „n silnia″. ↩︎
3. Undecylion to 10⁶⁶, czyli jedynka i sześćdziesiąt sześć zer. ↩︎
4. Krótko mówiąc, zapis a/bc traktuję jako równoważny a/(bc), a nie (a/b)c. ↩︎
5. Wygraną inną niż I stopnia traktujemy dla uproszczenia jako niepowodzenie. A czy poszczególne próby są naprawdę niezależne, zobaczymy w drugim odcinku. ↩︎