350
Kapitola 12: Vytvořující funkce
Cvičení
1. Podobným postupem jako v textu této části najděte
(a) průměrný počet líců, které padnou při n hodech mincí (se stejnou: pravděpodobností rubu i líce),
(b) průměrný počet šestek, které padnou při n hodech kostkou,
(c) * průměrnou hodnotu výrazu' (i - 6)2, kde i je počet hodů do první šestky (to je jakási míra „typické odchylky" od průměrného počtu, hodů, tj. od 6).
12.6   Náhodná procházka
Představme si číselnou osu nakreslenou v rovině, na níž jsou celá čísla:; vyznačena kroužky. Po těchto kroužcích se bude pohybovat figurka podle následujících pravidel náhodné procházky:
• Na začátku (před prvním tahem) stojí figurka v čísle 1.
« V každém tahu se pohne z čísla, kde právě stojí, buď o 2 čísla doprava nebo o 1 číslo doleva. Jedna z těchto možností se vždy zvolí náhodně, a obě možnosti mají stejnou pravděpodobnost (tj. jako bychom hodili mincí a rozhodli se podle výsledku hlava/orel).:
12.6.1 Úloha. Jaká je pravděpodobnost, že ůgurka vůbec někdy dospěje do čísla 0?
Nejdříve je potřeba vyjasnit, co se vůbec takovou pravděpodobností míní. Je celkem zřejmé, jak definovat pravděpodobnost, že se figurka aspoň jednou octne v 0 během prvních řekněme 7 tahů (označme ji Pj): Prvních 7 tahů náhodné procházky má 2 7 různých možných průběhů, protože v každém tahu se rozhodne mezi dvěma možnostim, a tato rozhodnutí lze libovolně zkombinovat. Podle pravidla nahodíte procházky v naší úloze jsou všechny tyto průběhy stejně pravděpodobné. Výše zmíněná pravděpodobnost P7 bude potom rovna počtu takových průběhů, které projdou 0 (čtenář si může ověřit, že je jich 75), dělenému celkovým počtem průběhů, tj. 27.
MĚĚ
lllllli
■H
12.6 Náhodná procházka
351
Hledanou pravděpodobnost P v naší úloze potom můžeme definovat jako limitu P — lim^oo Pj, kde definice Pí byla objasněna výše pro i — 7 (tato limita určitě existuje, protože zřejmě P\ < P% < ...).
Nechť a, značí počet průběhů prvních i tahů náhodné procházky takových, že figurka dorazí do 0 po i-tém. tahu, a zároveň nikdy předtím (tj. před 1., 2.,..., i-tým tahem) v 0 nebyla. Platí tedy
00
Zavedeme-li vytvořující funkci a(x) = a\x + a^x1 + azxz H----, máme
P = a{\).
Pro řešení úlohy bude užitečné podívat se i na procházky, které začínají v jiných číslech než 1 (ale pokračují podle stejného pravidla). Jaký bude například počet procházek začínajících v čísle 2, které dospějí poprvé do 0 v í-tém tahu (označme jej třeba J>i)? Aby taková procházka došla do 0, musí nejprve po nějakém j-tém tahu, 1 < j < i. poprvé dosáhnout čísla 1, a potom v dalších i —j tazích poprvé vstoupit do 0. Pro dosažení čísla 1 poprvé v j-tém kroku je a j možností, (jde totiž pouze o „posunutou kopii" procházky, která by začala v 1 a po j tazích došla do 0). Je-li figurka v j-tém kroku v 1, má ještě a i-j možností dosažení 0 po i — j dalších tazích. Celkem tedy dostaneme7
-31
v řeči vytvořujících funkcí to znamená b(x) = a(x)2.
Analogicky, q bude počet procházek začínajících v čísle 3, jež poprvé dorazí do 0 po i tazích. Podobně jako v předchozím nahlédneme že c(x) = a(x)b(x) = a(x)3.
Zkoumejme teď procházky začínající viz trochu jiného pohledu. : Při prvním tahu můžeme rovnou dojít do 0 (což dává ai = 1), nebo se octneme v čísle 3, a potom máme Ci_i možností, jak poprvé vstoupit
7Všimněte si, že jsme podstatně využili toho, že doleva se chodí vždy jen o 1, ■takže se nelze dostat z 2 do 0 a přitom přeskočit 1.
i;
■1
1
1
Ji
■
352
Kapitola 12: Vytvořující funkce
do 0 po dalších i — 1 tazích. Pro i > 1 tedy aj = Cj_i. Převedeno na vztah mezi vytvořujícími funkcemi
a(x) = x + xc(x) = x + xa(x)3. (12.8)
Speciálně pro x — i odtud dostaneme pro P = a(i) rovnici
P =
2 2
Ta má tři řešení, 1, (\/5 — 1)/2 a —+l)/2- Záporné řešení můžeme vyloučit ihned, a ani 1 nemůže být odpovědí v naší úloze (řada pro a(x) má nezáporné koeficienty a konverguje pro x ~ \, tedy definuje spojitou rostoucí funkci na intervalu [0, \], a proto hodnota a(|) je nej menší kladný kořen naší rovnice - rozmyslete si a případně nakreslete obrázek). Zbývá tedy P = — l)/2 = 0,618033988... a jedině toto číslo může být hledaná hodnota P (zase zlatý řez!).
Z rovnice (12.8) bychom v principu mohli spočítat i funkci a(x) a potom se snažit vyjádřit čísla a* třeba pomocí jejího Taylorova rozvoje (což je ale dost pracné). Půvab výše uvedeného řešení je v tom, že jsme nic takového dělat nepotřebovali.
Cvičení
1. Uvažme náhodnou procházku začínající v 0, při níž se postupuje o 1 číslo doleva nebo o 1 číslo doprava, každá volba má pravděpodobnost 1.
(a) * Dokažte, že s pravděpodobností 1 se někdy vrátíme do 0.
(b) Dokažte, že každé číslo k někdy navštívíme, s pravděpodobností 1.
12.7 Rozklady
Kolika způsoby můžeme napsat přirozené číslo n jako součet několika : přirozených čísel? Odpověď není těžká, pokud počítáme uspořádané rozklady, což znamená, že zápisy 3™2 + la3=l + 2 považujeme za dva různé rozklady čísla 3 (cvičení 1). Mnohem těžší a zajímavější otázku dostaneme, považujeme-li za stejné dva rozklady, jež se
12.7 Rozklady
353
liší pouze pořadím sčítanců (v tomto případě budeme v tomto oddílu mluvit prostě o rozkladech čísla n). Například pro n = 5 jsou všechny možné rozklady 5 = 1 + 1 + 1 + 1 + 1,5 = 1 + 1 + 1 + 2,5 = 1 + 2 + 2, 5 — 1 + 1 + 3,5 = 2 + 3,5 = l + 4a5 = 5. Označme pn počet rozkladů čísla n v tomto smyslu.
Abychom učinili zápis rozkladu jednoznačným, můžeme například požadovat, aby sčítance byly seřazeny vzestupně, jako jsme je psali v seznamu všech rozkladů čísla 5. Takže jiná formulace otázky o počtu rozkladů je: Kolika způsoby můžeme postavit z n cihel „neklesající zeď" jako na následujícím obrázku (který odpovídá rozkladům 10= 1 + 1 + 2 + 2 + 4 a 10 = 1 + 1 + 2 + 61?
(Takový obrázek se nazývá Ferrersův diagram daného rozkladu.)
Definice pn vypadá jednoduše, takže čtenáře, ze středoškolských příkladů třeba zvyklého, že na všechno je vzoreček, může překvapit, že pro pn žádný jednoduchý vzorec, něco jako třeba binomický koeficient, není. Problém odhadu čísla pn se studoval v teorii čísel, a v roce 1918 ho s neuvěřitelnou přesností vyřešili Hardy a Ramanujan. (Tuto historii popisuje Littlewood v knížečce [18], již můžeme doporučit jako skvělé čtení o matematice.) Dokonce objevili přesný (ale komplikovaný) vzorec pro pn- Porozumění tomuto výsledku, nemluvě o jeho důkazu, vyžaduje poměrně hluboké znalosti z teorie čísel (viz například Andrews [2]). Tady budeme mnohem skromnější: poměrně dobré asymptotické odhady pro pn se dají dokázat jednoduše, i když rafinovaně, pomocí vytvořujících funkcí, a to zde předvedeme.
Už víme, jak vyjádřit počet řešení rovnice
h + Í2 +----1- ife
n.
s hodnotami každé proměnné i j ležícími v nějaké předepsané množině, jako koeficient u xn ve vhodném výrazu. Pro náš problém ale nezáleží na pořadí těch íj, takže není vidět, jak to uvést do souvislosti s (neuspořádanými) rozklady čísla n. Trik je považovat i j za přisp ě-