Matematika III, 13. cvičení
Pojmy k zopakování
• Vytvořující funkce dané posloupnosti
• Operace s vytvořujícími funkcemi
• Zobecněná binomická věta
• Lineární rekurence
• Catalanova čísla
• Fibonacciho čísla
Příklad 266. Určete vytvořující funkce následujících posloupností
1. (1;2;1;4;1;8;1;16;...)
2. (1;1;0; 1; 1; 0; 1; 1;.. .)
3. (l;-l;2;-2;3;-3;4;-4;...) Výsledek.     1. +
2. Ä
1—x°
ó-   (1-x2)2 (1-x2)2
Příklad 267. Určete koeficient u x17 v (x3 + x4 + x5 + ... )3 Výsledek. 45
Příklad 268. V krabici je 30 červených, 40 modrých a 50 bílých míčků (míčky téže barvy jsou nervzpoznatelné). Kolik je různých možností, jak z takovéto krabice vybrat soubor 70 míčků?
Výsledek. (722) - (?) - (?) - (?)
Příklad 269. Jaká je pravděpodobnost, že při hodu 12 hracími kostkami padne součet 30?
Nápověda: Vyjádřete počet všech možností, kdy padne součet 30. Uvažujte (x + x2 + x3 + X4 + X5 +x6)12.
Výsledek. Q - 12 • (23) + 66 • (£) - 220 • Q
Příklad 270. Sadař má vysadit 25 nových stromků, přičemž má k dispozici pouze 4 druhy. Sadařova manželka si však klade omezující podmínky: nejvýše jeden ořešák, nejvýše 10 jabloní, alespoň 6 třešní a alespoň 8 sliv oni Kolik existuje různých způsobů výběru druhů stromů? Nápověda: Zajímá nás koeficient u x25 v
(1 + x)(l + x H-----h x10)(x6 + x7 + ... )(x8 +x9 + ...).
Výsledek. Q-Q-Q.
Příklad 271. Vyjádřete obecný člen posloupností určených následujícími rekurencemi: 1. di = 3, ci2 = 5, an+2 = 4an+i — 3an pro n = 1, 2, 3....
46
2. ao = O,cii = 1, fl(!+2 = 2an+i — 4an pro n = 0,1, 2, 3 ....
Příklad 272. Řešte rekurenci, kde v posloupnosti (a^, ai, a2,...) Je následující člen aritmetickým průměrem předchozích dvou.
Výsledek. an = k +
Příklad 273. Řešte rekurenci an+2 = y/o-n+io-n s počátečními podmínkami clq = 2,ai = 8. Nápověda: Utvořte novou posloupnost bn = log2an.
Příklad 274. Spočtěte počet triangulací konvexního n-úhelníku.
Nápověda: Vyberme libovolnou úhlopříčku jdoucí pevným vrcholem. Ta nám mnohoúhelnk rozdělí na dva.
Výsledek. tn = Cn_2, kde Cn značí Catalanovo číslo.
Příklad 275. Určete počet procházek ve čtvercové síti o rozměrech n x n z levého dolního rohu A do pravého horního rohu B, které vedou pouze doprava a nahoru takových, že mají právě jeden bod na diagonále AB (nepočítaje A a B). Nápověda: Catalanova čísla.
Příklad 276. Dokažte, že pro Fibonacciho čísla platí:
1. F2 + F4 + --- + F2n = F2n+i - 1
2. F1 + F3 + • • • + F2ll-i = F2n
Příklad 277. Označme Hn minimální počet kroků potřebných k přemístění věže o n kotoučích z jednoho kolíku na druhý u hlavolamu Hanojská věž. Odvoďte rekurentní formuli pro výpočet Hn a určet její obecné řešení.
Výsledek. Hn+1 = 2Hn + 1, Hn = T1'1
47