Matematika III - 13. přednáška Aplikace vytvořujících funkcí
Michal Bulant
Masarykova univerzita Fakulta informatiky
11. 12. 2007
Obsai
Vytvořující funkce
Q Řešení reku
renci
•  H. S. Wilf, Generatingfunctionology, Academie Press, druhé vydaní, 1994 , (rovněž
http://www.math.upenn.edu/~wilf/DownldGF.html)
•  R. Graham, D. Knuth, 0. Patashnik, Concrete Mathematics, druhé vydání, Addison-Wesley, 1994.
•  Martin Panák, Jan Slovák, Drsná matematika, e-text.
•  Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s.
0paková
Definice						
(Obyčejnou) vytvořující funkcí		posloupnosti a	= (•	Jo, ai	,^2	• ••)
rozumíme	mocninnou řadu oo y^ anx" = a0 + a\ n=0	x + a2x2 + a3x3	+ •			
Exponenc	iální vytvořující fun	ccí posloupnosti	a =	= (a0,	31,	32,...)
pak rozumíme mocninnou řadu						
	°°      x" /3n—r = a0 + ai n=Q	2        3 X               X           X l!+a22!+3!	+ •			
Poznámka
Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru x" hraje n~x), ale těmi se zde zabývat nebudeme.
Poznámka
(Nejen) pro manipulace se sumami používají autoři Concrete
mathematics velmi vhodné označení [logický predikát} -
výraz je roven 1 v případě splnění predikátu, 0 v případě jeho
nesplnění.
Např. [n = 1], [2|n] apod.
Pro vyjádření koeficientu u x" ve vytvořující funkci F(x) se pak
často používá zápis [x"]F(x).
•  Sčítání dvou posloupností člen po členu.
•  Vynásobení všech členů posloupnosti stejným skalárem.
•   Posunutí posloupnosti doprava.
•   Posunutí posloupnosti doleva.
•  Vynásobení n-tého členu posloupnosti skalárem a".
•   „Nafouknutí" posloupnosti nulami.
•  Vynásobení n-tého členu posloupnosti číslem n.
•  Vydělení n-tého členu posloupnosti číslem n.
a Konvoluce posloupností cn = J2o<k<nakbn-k-
In
1-x
1 1-x
n>0
n>l v—«, x"
n>0
smx
cosx
B-i>"i£
,2n+l
n>0
(2/1 + 1)!'
Ec-1)"
,2n
n>0
(2n)ľ
(1,1,1,...
Ill (0,1,-,-,-...
(1'1'2'6'24"" (0,1,0,-jU^,...
(1,0,-i,o,— ),0,...
fc>0 v   7                                     \ /     \ /
-L-= £(-l)V,                           (1,-1,1,-1,...
n>0
—[— = X>|n]xn,               (1, O,..., 0,1, O,..., 0,1,...
(l_1x)2=E(n + 1)x"'                              (1,2,3,4,5,...
(1, r,r2,r2,r3,... 111
1 — rx      ^—' ln(l+x) = ^-(-l)"+V
(0,1
'           r\  5    O  5            yl   1   •   '   '
r y  4
Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí. Tím je míněno vyjádření členu an jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků:
O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0).
O Obě strany rovnice vynásobíme x" a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anx", což je vytvořující funkce A{x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A{x).
O Zjištěná rovnice se vyřeší vzhledem k A(x).
O Výsledné A(x) se rozvine do mocninné řady, přičemž koeficient u x" udává an, tj. an = [x"]A(x) .
Jak jsme již viděli na příkladu Fibonacciho posloupnosti, v kroku 4 často s výhodou využijeme rozkladu na parciální zlomky. Ten
jsme již viděli dříve (často se používá při integraci racionálních lomených funkcí), proto připomeneme jen stručně:
•   Předpokládáme, že P(x)/Q(x) je podíl polynomů, kde
st P < st Q (jinak vydělíme se zbytkem) a P(x), Q(x) nemají společné kořeny.
•   Polynom Q(x) rozložíme na kořenové činitele.
» Jsou-li všechny kořeny ai,... ,ag jednoduché, pak
<?(X)
OL\
+ ••• +
tt£
Má-li kořen a násobnost k, pak jsou příslušné parciální zlomky
tvaru
Ai       ,       A2                            Ak
(x — a)     (x — a)2             (x — a)
k-
•  V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/(x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. (V našich úlohách ale raději rozložíme i kvadratické faktory na lineární výpočtem kořenů
vC.)
•   Neznámé dopočítáme buď roznásobením a porovnáním koeficientům u jednotlivých mocnin x nebo dosazením jednotlivých kořenů.
•  Výrazy A/(x — a)k převedeme na výrazy tvaru B/(l — ßx)k vydělením čitatele i jmenovatele výrazem (—a)k. Tento výraz již umíme rozvinout do mocninné řady.
S využitím vytvořujících funkcí určíme formuli pro počet bn pěstovaných binárních stromů na n vrcholech. Prozkoumáním případů pro malá n vidíme, že
b0 = 1, bi = 1, fc = 2, b3 = 5.
Snadno nahlédneme, že pro n > 1 vyhovuje bn rekurentní formuli
bn = bobn-i + b\bn-2 H---------h bn-ibo.
Vidíme, že jde vlastně o konvoluci posloupností. Vztah upravíme, aby platil pro všechna n G Nq\
bn =   Y^   bkbn_k_x + [n = 0].
0<k<n
Tím máme hotov krok 1.
V kroku 2 vynásobíme obě strany x" a sečteme. Je-li B{x) odpovídající vytvořující funkce, pak:
B{x) = J2 bnx" = Y, bkbn-k-ix" + J> = °K --
n,k
n,k
Y,bkxk ľ^bn-k-ix"-^ +1 = : Y, bkxk(xB(x)) + 1 = B(x) ■ xB(x) + 1.
k
Pozorný čtenář si jistě povšiml, že ve výše uvedeném výpočtu jsme nahradili konvoluci bn = bobn-\ + b\bn-i + • • • + bn-\bo vztahem
bn = bobn-i H--------h bn-ibo + bnb-\ + bn+1b-2 H------. Díky naší
konvenci to ale není problém a velmi to usnadňuje práci se sumami (s nekonečnými součty se zde pracuje podstatně snadněji než s konečnými, kdy musíme neustále hlídat meze).
V kroku 3 řešíme kvadratickou rovnici B{x) = xB{x)2 + 1 pro E(x) :
= 1±VTHÍE v  '                2x
Znaménko + ale nepřichází v úvahu, protože pak by pro x —> 0_| B{x) měla limitu oo, zatímco vytvořující funkce pro naši posloupnost musí mít v 0 hodnotu bo = 1. Zbývá už pouze krok 4, tedy rozvinout B{x) do mocninné řady. Rozvoj získáme pomocí zobecněné binomické věty
k>0  V        7                                k>l
a po vydělení 1 — \/l — 4x výrazem 2x dostaneme
2k\k-l
(-4x)*
n>0
n + 1
n>0
n J n + 1
4
Dokázali jsme, že počet binárních pěstovaných stromů na n vrcholech je roven bn = -^ (2n") - tato významná posloupnost se nazývá posloupnost Catalanových čísel. Kromě toho, že Catalanova čísla vyjadřují počet binárních pěstovaných stromů, vystupují rovněž jako:
•   počet slov délky 2n obsahujících n znaků X a V takových, že žádný prefix slova neobsahuje více Y než X
•  podobně takové fronty u pokladny (5koruny a lOkoruny), že nezásobená pokladna může vždy vrátit
•   počet korektně uzávorkovaných výrazů složených z levých a pravých závorek
•   počet monotónních cest z [0,0] do [n, n] podél stran jednotkových čtverců, které nepřekročí diagonálu
•   počet různých triangulací konvexního (n + 2)-úhelníku.
Vytvořující funkce
ooooo
Ještě
Příklad
Vyřešte rekurenci
■?0 = 3\ = 1
a„ = a„_i + 2a„_2 + (-!)"
Tato rekurence je opět jiného typu než dosud studované. Jako vždy neuškodí vypsání prvních několika členů posloupnosti (teď ale ani moc nepomůže, snad jen pro kontrolu správnosti výsledku).3
"Narozdíl od tvrzení v Concrete mathematics je již možné tuto posloupnost nalézt v The On-Line Encyclopedia of Integer Sequences.
Řešení (pokr.)     _________________________________________1	
• Krok 1: an = a„_i + 2a„_2 + (-l)"[n > 0] + [n =	= !]•
• Krok 2: A(x) = xA(x) + 2x2A(x) + ^ + x.	
• Krok 3:	
^Xj-(l-2x)(l+x)2-	
• Krok 4: a„ = |2" + (±n + §) (-1)".	
Reku
Někdy dokážeme snadno vyjádřit hledaný počet jen pomocí více vzájemně provázaných posloupností.
Příklad
Kolika způsoby můžeme pokrýt (nerozlíšenými) kostkami domina obdélník 3 x n?
Snadno zjistíme, že c\ = 0, c2 = 3, C3 = 0, dále klademe cq = 1 (nejde jen o konvenci, má to svou logiku).
Najdeme rekurzívní vztah - diskusí chování „na kraji" zjistíme, že cn = 2r„_i + c„_2, rn = c„_2 + rn_2, r0 = 0, rx = 1, kde rn je počet pokrytí obdélníku 3 x n, ze kterého jsme odstranili levý horní roh.
Řešení (pokr.)
•  Krok 1: cn = 2r„_i + c„_2 + [n = 0],     rn = u„_i + r„_2.
•  Krok 2:
C(x) = 2x/?(x) + x2 C(x) + 1,     R(x) = xC(x) + x2 /?(x).
•  Krok 3:
1       ~2
C(x)
/?(x)
l-4x2+x4'        "vv      l-4x2+x4'
• Krok 4: Vidíme, že obě funkce jsou funkcemi z2, ušetříme si práci tím, že uvážíme funkci D(x) = 1/(1 — 4x + x2), pak totiž C(x) = (l-x2)D(x2), tj.
[x2"]C(x) = [x2"](l -x2)D(x2) = [x"](l -x)D(x), a tedy Qn = dn — dn-\.
Řešení (závěr)
Kořeny 1 — 4x + x2 jsou 2 + a/3 a 2 — a/3 a již standardním způsobem obdržíme
(2 +a/3)"     (2-a/3)"
Qn = —-------— +
V^
3 + a/3
Podobně jako u Fibonacciho posloupnosti je druhý sčítanec pro velká n zanedbatelný a pro všechna n leží mezi 0 a 1, proto
Qn
(2 +a/3)"
3-a/3
Např. C20 = 413403.