'Teorie grafů
MB103 - podzim 2010 Cvičení 6
Pojmy k zopakování:
• Vytvořující funkce dane posloupnosti
• Operace s vytvořujícími funkcemi
• Zobecnená binomická veta
• Linearní rekurence
• Catalanova čísla
• Fibonacciho císla
Příklad 1. Urcete vytvorující funkce nasledujících posloupností
1. (1;2;1;4;1;8;1;16;...)
2. (1; 1;0; 1; 1; 0; 1; 1; ...)
3. (1;-1;2;-2; 3; -3; 4; -4;...) Výsledek.     1. ^ + 2x
1-x2    1 l-2íE2
2.
1+x 1—x3
3.    C1    „212 +
(1-x2)2   1 (1-x2)2
Řešení     1. (1; 2; 1; 4; 1; 8; 1; 16;...) = (1; 0; 1; 0;...) + (0; 2; 0; 4; 0; 16;...). Urcíme tedy
vytvorující funkce jednotlivých posloupností. První dostaneme z posloupnosti (1,1,1,1,1). Její vytvorující funkce je      . Nuly vnoríme nahrazením x  za x. Podobne druhou vytvorující funkci dostaneme z posloupnosti (1; 2; 4; 8; 16;...). Nejprve vynísobíme dvema, vložíme nuly a pak vynasobením x dostaneme nulu na zacatku.
2. (1; 1;0; 1; 1; 0; 1; 1;...) = (1; 0; 0; 1; 0; 0; 1...) + (0; 1; 0; 0; 1; 0; 0; 1...).
Příklad 2. Urcete koeficient u x17 v (x3 + x4 + x5 + ... )3
Výsledek. 45
Řešení. (x3 + x4 + x5 + ...)3 = (^-x^ = x9 • (1-1x)3. Zajíma nís tedy koeficient u x8 v (1-1x)3. Ten je roven (12°), tedy 45.
Příklad 3. V krabici je 30 cerveních, 40 modrích a 50 bílích mícku (míccky teze barvy jsou nerozpoznatelne). Kolik je ruznych mozností, jak z takoveto krabice vybrat soubor 70 mícku?
x
Výsledek. (?) - (?) - (?) - (?)
Řešeni. Počet možností je zřejmě roven koeficientu u x70 v
(1 + x + • + x30)(1 + x + • + x40)(1 + x + • + x50). Když upravíme, dostáváme, že
(1 + x + • • • + x30)(1 + x + • • • + x40)(1 + x + • • • + x50) =      1 .3 ... (1 -x31)(1 -x41 )(1 -x51).
(1 — x)3
Řešení pak dostáváme že žobecnene binomické vety.
Příklad 4. Jaká je pravdepodobnost, že pri hodu 12 hracími kostkami padne součet 30?
Nápověda: Vyjádřete počet všech možnosti,, kdy padne součet 30. Uvazujte (x + x2 + x3 + x4 + x5 + x6)12.
Vásledek. (11) - 12 • © + 66 • g[) - 220 • Q
Resená. Vísledna pravdepodobnost bude podílem počtu prížnivích a vsech možností. Počet vsech možností je 612. Spočítejme nyní počet prížnivích možností. Uvažujme vyraž (x + x2 + x3 + x4 + x5 + x6)12. Počet prížnivych možností je potom koeficient u x30. Upravujme:
(x + x2 + x3 + x4 + x5 + x6)12 =(x(1 -       12 = x12 •(i—^^ 12
1 - x 1 - x
Zajíma nas tedy koeficient u x18 u
f
1   x6 12 1 12
1 - x 6       12        18 1
,    = (1 - 12x6 + 66x12 - 220x18) . x J 1 - x
Ze žobecnene binomicke vety pak dostavíme počet prížnivích možností
(11)-12 ■ (20+66(1D- -G1)
Příklad 5. Sadar ma vysadit 25 novych stromku, pričemž ma k dispožici použe 4 druhy. Sadarova manželka si vsak klade omežující podmínky: nejvíse jeden oresak, nejvíse 10 jabloní, alespoň 6 tresní a alespoň 8 slivoní Kolik existuje ružnych žpusobu víberu druhu stromu?
Nápověda: Zajámá nás koeficient u x25 v
(1 + x)(1 + x + • • • + x10)(x6 + x7 + ... )(x8 + x9 + ...). Výsledek. (14) - ff) - (3).
Řešeni.
(1 + x)(1 + x + • • • + x1Q)(x6 + x7 + ... )(x8 + x9 + ... )
x14(1 - x2)(1 - x11)
Tedy nás zajímá koeficient u x11 ve (1 — x2 — x11...)
1
Příklad 6. Vyjádřete obecná clen posloupností určeních následujícími rekurencemi:
1. 01 = 3, 02 = 5, ara+2 = 4ara+1 — 3a„ pro n = 1, 2, 3----
2.  <°q = °,O1 = 1 On+2 = 2on+1
4on pro n = 0,1, 2, 3 ....
Řešeni.
1. an = 2 + 3n-1.
2. On = 1v/—3 • ((1 + v/—3)n
2
(1 — v/—3)n).
Příklad 7. Reste rekurenci, kde v posloupnosti (oq, o1, o2, ...) je následující clen aritme-
Příklad 8. Reste rekurenci on+2 = ^on+1on s pocátecními podmínkami oq = 2, o1 = 8. Nápověda: Utvořte novou posloupnost bn = log2 on.
Příklad 9. Spoctete pocet triangulací konvexního n-áhelníku.
Napovedá: Vyberme libovolnou úhlopříčku jdoucí pevným vrcholem. Ta nám mnohoUhelnk rozdelí na dva.
Výsledek. tn = Cn-2, kde Cn znací Catalanovo císlo.
Příklad 10. Urcete pocet procházek ve ctvercove síti o rozmerech n x n z leveho dolního rohu A do praveho horního rohu B, ktere vedou pouze doprava a nahoru takovách, ze mají práve jeden bod na diagonále AB (nepocítaje A a B). Napoveda: Catalanova čísla.
Příklad 11. Dokazte, ze pro Fibonacciho císla platí:
1. F2 + F4 + ■ ■ ■ + F2n = F2n+1 — 1
2. F1 + F3 + ^ ^ ^ + F2n-1 = F2n
Příklad 12. Oznacme Hn minimální pocet kroku potrebních k premístení veže o n ko-toucích z jednoho kolíku na druhá u hlavolamu Hanojská vez. Odvod'te rekurentní formuli pro vípocet Hn a urcet její obecne resení.
tickym prumerem predchozích dvou.
Vásledek. on = k
+1.
Výsledek. Hn+1 = 2Hn + 1, Hn = 2n-1