Genererande funktion

En genererande funktion är inom matematik en formell potensserie som innehåller information om en talföljd.

Definition

Den genererande funktionen f till talföljden a_n, n = 0, 1, 2, ..., definieras som

$f(x)=\sum _{k=0}^{\mathrm{\infty }}{a}_k{x}^k$

Ofta är f bara definierad i ett intervall runt origo (ibland bara i en punkt), nämligen när summan bara konvergerar där. Det är då mer fruktbart att betrakta f som en formell potensserie snarare än en funktion.

Om a_n är sannolikhetsfördelningen av en diskret slumpvariabel så är dess genererande funktion kallad en sannolikhetsgenererande funktion.

Exponentiell genererande funktion

Ibland betraktas istället en exponentiell genererande funktion till en talföljd a_n, definierad som:

$\sum _{k=0}^{\mathrm{\infty }}\frac{a_k}{k!}{x}^k$.

Exempel

Den genererande funktionen till Fibonacciföljden F_n kan bestämmas som följer:

F_n definieras av rekursionen $F_{k+2}-F_{k+1}-F_k=0$, och $F_0=0,F_1=1$

Genom att sätta $f(x)=\sum _{k=0}^{\mathrm{\infty }}{F}_k{x}^k$ kan vi ställa upp

$(1-x-x^2)\cdot f(x)=$

Substituera f(x)

$=(1-x-x^2)\cdot \left(\sum _{k=0}^{\mathrm{\infty }}{F}_k{x}^k\right)=$

Multiplicera in i parentesen

$=\sum _{k=0}^{\mathrm{\infty }}{F}_k{x}^k-\sum _{k=0}^{\mathrm{\infty }}{F}_k{x}^{k+1}-\sum _{k=0}^{\mathrm{\infty }}{F}_k{x}^{k+2}=$

Förskjut indexen med 0, 1 respektive 2 steg

$=\sum _{k=0}^{\mathrm{\infty }}{F}_k{x}^k-\sum _{k=1}^{\mathrm{\infty }}{F}_{k-1}{x}^k-\sum _{k=2}^{\mathrm{\infty }}{F}_{k-2}{x}^k=$

Ta ut k = 0 och k = 1

$=(F_0\cdot x^0+F_1\cdot x+\sum _{k=2}^{\mathrm{\infty }}{F}_k{x}^k)-(F_{1-1}\cdot x^1+\sum _{k=2}^{\mathrm{\infty }}{F}_{k-1}{x}^k)-\left(\sum _{k=2}^{\mathrm{\infty }}{F}_{k-2}{x}^k\right)=$

Slå ihop resterande summor

$=F_0+F_1\cdot x-F_0\cdot x+\sum _{k=2}^{\mathrm{\infty }}(F_k-F_{k-1}-F_{k-2})\cdot x^k$

Sätt in F₀ = 0, F₁ = 1 och rekursionen

$=0+1\cdot x-0\cdot x+\sum _{k=2}^{\mathrm{\infty }}0\cdot x^k=x$

Alltså gäller

$f(x)=\frac{x}{1-x-x^2}$

Externa länkar

• archive.org: Genererandefunktioner