generating function

generating function (tsz. generating functions)

1. (informatika) generátorfüggvény

A generálófüggvény egy hatékony eszköz a diszkrét matematikában, különösen kombinatorikában és sorozatok elemzésében, amely lehetővé teszi, hogy egy sorozatot egy formális hatványsorral reprezentáljunk. Segítségével algebrai módszerekkel lehet dolgozni sorozatokkal.

Egy ${\textstyle a_{0},a_{1},a_{2},\dots }$ sorozat generálófüggvénye a következő hatványsor:

$${\displaystyle G(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\dots =\sum _{n=0}^{\infty }a_{n}x^{n}}$$

Ezt hívjuk hagyományos generálófüggvénynek (ordinary generating function, OGF).

• Sorozatok összefoglalása kompakt módon
• Rekurziók megoldása (pl. Fibonacci)
• Kombinatorikus problémák algebrai kezelése
• Zárt formulák megtalálása

$${\displaystyle G(x)=1+x+x^{2}+x^{3}+\dots ={\frac {1}{1-x}},\quad |x|<1}$$

$${\displaystyle G(x)=0+x+2x^{2}+3x^{3}+\dots ={\frac {x}{(1-x)^{2}}}}$$

$${\displaystyle F(x)=x+x^{2}+2x^{3}+3x^{4}+5x^{5}+\dots ={\frac {x}{1-x-x^{2}}}}$$

• Rekurzív formulák megoldása: Pl. ${\textstyle a_{n}=a_{n-1}+a_{n-2}}$ Fibonacci-típusú relációk
• Kombinatorikai feladatok: pl. kollekciók számlálása
• Valószínűségszámítás: pl. diszkrét valószínűségi eloszlások kezelése
• Algoritmus-analízis: pl. várható értékek, algoritmus futásidő elemzése

from sympy import symbols, simplify

x = symbols('x')
fibonacci_gf = x / (1 - x - x**2)
print("F(x) =", simplify(fibonacci_gf))

Típus	Leírás
OGF (ordinary generating fn.)	${\textstyle \sum a_{n}x^{n}}$
EGF (exponential generating fn.)	${\textstyle \sum {\frac {a_{n}x^{n}}{n!}}}$
Dirichlet generating function	${\textstyle \sum {\frac {a_{n}}{n^{s}}}}$, gyakran számelméletben

• A generálófüggvény nem mindig konvergens függvényként értelmezve.
• Formális hatványsorként kezelve elég, ha algebrai szabályok szerint működik.
• Analitikus kombinatorika alapja.

• generating function - Szótár.net (en-hu)
• generating function - Sztaki (en-hu)
• generating function - Merriam–Webster
• generating function - Cambridge
• generating function - WordNet
• generating function - Яндекс (en-ru)
• generating function - Google (en-hu)
• generating function - Wikidata
• generating function - Wikipédia (angol)