generating function

Angol

Főnév

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.

---

📐 Alapdefiníció

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

$$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).

---

🧠 Miért hasznos?

• 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

---

📊 Példák

1. Állandó sorozat: ${\textstyle a_{n}=1}$

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

2. Aritmetikai sorozat: ${\textstyle a_{n}=n}$

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

3. Fibonacci-sorozat

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

---

🔧 Alkalmazások

• 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

---

💻 Példa: Generálófüggvény Fibonaccihoz Pythonban

from sympy import symbols, simplify

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

---

🧮 Fontos típusok

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

---

📘 Megjegyzések

• 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.

További információk

• 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)