4. Generátor függvények

Question 1

Generátorfüggvény definíció

Answer 1

A generátorfüggvényt használjuk a matematikai rekurziók n-edik tagjának meghatározására, mint például a Fibonacci-számoknál. Ez egy olyan függvény, amelyet a sorozat elemeinek segítségével definiálunk, és lehetővé teszi a sorozat bármely elemének kiszámítását.

Question 2

Generátor függvény alap képlete

Answer 2

F(x):=\sum^{\infty}_{n=0}a_nx^n

A generátorfüggvényt az alábbi módon definiáljuk: Legyen $(a_n)$ egy tetszőleges sorozat, és legyen $F(x)$ az $a_n$ sorozat generátorfüggvénye. Ekkor $F(x)$ a következőképpen adható meg:

$F(x) = \sum^{\infty}_{n=0}a_nx^n$

Ez azt jelenti, hogy a generátorfüggvény kifejezi a sorozat elemeit a hatványfüggvények (az $x$ hatványainak) lineáris kombinációjaként.

Question 3

Tetszőleges $x,a \in \cnums$ komplex számokra, $|x|<|a|$ esetén

Answer 3

\frac{1}{x-a}=\sum^{\infty}_{n=0}\frac{-1}{a^{n+1}}*x^n

Question 4

Összefüggés a racionális törtfüggvények és állandó együtthatójú lineáris homogén rekurziók között

Answer 4

• nevezőjének x=0 nem győke
• a sorozat kielégít egy állandó együtthatójú homogén lineáris k-adrendű rekrziót
• továbbá a generátorfüggvény nevezőjéből leolvasható a k.é.p. is

Egy tetszőleges $(a_n) ⊂ C$ sorozat generátorfüggvénye pontosan akkor egy racionális törtfüggvény, mely nevezőjének az $x=0$ nem gyöke, az $(a_n)$ sorozat kielégít egy állandó együtthatójú homogén lineáris k-adrrendű rekurziót, továbbá a generátor függvény nevezőjéből leolvasható (egyszerűen), és még kezdeti érték probléma is.

Ezek az összefüggések azt jelzik, hogy ha egy sorozat generátorfüggvénye racionális törtfüggvény, akkor a sorozat kielégít egy állandó együtthatójú lineáris homogén rekurziót. Ezenkívül a generátorfüggvény nevezőjéből leolvashatóak a sorozat kezdeti értékei a kezdeti érték probléma megoldásához.

Question 5

Catalan számok

Answer 5

A
$t_{n+1}:= \sum^{n}{i=0}t_i*t{n-i}, t_0=1$
rekurziót kielégítő sorozat explicit alakja
$t_n =\frac{1}{n + 1}\binom{2n}{n}$

Question 6

Hanoi tornyai:

Answer 6

Az összefüggés alapján $(h_n)$ sorozat $H(x)$ generátor függvénye

$H(x) = \frac{x}{(1-x)(1-2x)} = \frac{x}{2x^2-3x+1}$

így a 6.6 tétel összefüggése alapján $(h_n)$ sorozat kielégíti a

$h_n = 3h_{n-1}-2h_{n-2}$

állandó e.h.-jú homogén lineáris rekurziót.

A kapott összefüggést könnyű teljes indukcióval igazolni, feltéve ha ismerjük az $h_n = 2^n-1$ explicit képletet…

Question 7

Pénzváltási probléma

Answer 7

Hányféle képpen lehet n forintot felváltani mondjuk 3,7,11 ft-os bankjeggyel? (Ezek a számok egymáshoz képest relatív prímek

Ha $(a_n)$ jelöli a

$h_1y_1 + … + h_ky_k = n$

egyenlet nemnegatív egész gyökeinek számát adott $h_1, … h_k \in \N,\ h_i \neq 0, k \in \N$ tetszőleges rögzített pozitív egész számok esetén, $n \in \N\ és\ F(x) := \sum_{n=1}^{\infty}\ az\ (a_n)$ sorozat generátorfüggvénye, akkor

$F(x) = \frac{1}{(1-x^{h1})· … · (1-x^{h_k})}$