Genereringsfunksjonen

Genereringsfunksjonen er en måte å lagre en følge av tall i form av en formell potenserrekke. Den vanligste varianten er den ordinære genereringsfunksjonen (OGF): G(x) = sum_{n>=0} a_n x^n, der koeffisientene a_n utgjør følgen. En annen viktig variant er den eksponentielle genereringsfunksjonen (EGF): A(z) = sum_{n>=0} a_n z^n / n!. Genereringsfunksjoner brukes i hovedsak i kombinatorikk og telleproblemer for å omforme rekursive forhold til algebraiske ligninger og dermed finne lukrede uttrykk eller asymptotiske estimater.

Et enkelt eksempel er følgen a_n = 1 for alle n. Da er G(x) = 1 + x + x^2 + ... = 1/(1-x) for |x| < 1. For følgen a_n = n blir G(x) = sum_{n>=0} n x^n = x/(1-x)^2. For eksponentialgenereringsfunksjonen, er EGF-en for a_n = 1 lik e^z, og for a_n = n er den lik z e^z. Slike eksempler illustrerer hvordan algebraiske operasjoner på genereringsfunksjoner til sammenlignbare følger kan føre til nye innsikter og kalkulasjonsformer.

Bruk av genereringsfunksjoner omfatter løsning av rekursjoner, beregning av telleverdier i komplekse kombinasjonsklasser, samt analyse av vekst og asymptotikk. Konseptet opererer ofte som et verktøy i både formal og analytisk forstand, der man behandler genereringsfunksjoner som formelle series uten nødvendigvis å kreve konvergens, eller som analytiske funksjoner der konvergens og singulariteter gir asymptotiske resultater.

Historisk ble ideen om genereringsfunksjoner utviklet av blant andre Leonhard Euler og ble senere utvidet av Pólya, Riordan og andre innen kombinatorikk og katologi.