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

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

Rekurzió: $t_{n+1}:= \sum^{n}{i=0}t_i*t{n-i}, t_0=1$

Generátor függvény: $F(x):= \sum^{\infty}_{n=0}t_nx^n$

Összefüggés a gen. fv.-re a rekurzió alapján: $F(x) = x · F^2(x) + t_0$

Catalan számok végeredménye: $t_n =\frac{1}{n + 1}\binom{2n}{n}$

Question 6

Hanoi tornyai:

Answer 6

Rekurzió: $h_{n+1} = 2h_{n} + 1 , h_0 = 0 , h_1 = 1$

Generátor függvény: $F(x) :=\sum^∞_{n=0}h_nx^n$

Összefüggés a gen. fv.-re a rekurzió alapján: $H(x) = \frac{x}{(1 − x)(1 − 2x)}$

Lépések számának végeredménye n korong esetén: $h_n = 2^n − 1$

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

Legyenek adottak a $h_1, …, h_k ∈ \N$ , $h_i \neq 0, k ∈ \N$ tetszőleges rögzített pozitív egész számok. Hány nemnegatív egész gyöke van ó tetszőleges n ∈ N természetes szám esetén a $h_1y_1+, …, +h_ky_k = n$ egyenletnek?

$F(x):=\sum^{\infty}_{n=0}a_n*x^n$ ahol $a_n$-el az egyenlet nemnegatív egész gyökeinek számát jelöljük $n ∈ \N$ esetén.

Ekkor $F(x):=\sum^{\infty}_{n=0}a_nx^{h_1y_1+h_2y_2+,…,+h_ky_k}=\frac{1}{(a-x^{h_1})…*(1-x^{h_k})}$