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

${\displaystyle f(x)=\sum _{k=0}^{\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.

Exempel

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

F_n definieras av rekursionen ${\displaystyle F_{k+2}-F_{k+1}-F_{k}=0\ }$, och ${\displaystyle F_{0}=0,F_{1}=1\ }$

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

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

Substituera f(x)

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

Multiplicera in i parentesen

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

Förskjut indexen med 0, 1 respektive 2 steg

${\displaystyle =\sum _{k=0}^{\infty }F_{k}x^{k}-\sum _{k=1}^{\infty }F_{k-1}x^{k}-\sum _{k=2}^{\infty }F_{k-2}x^{k}=}$

Ta ut k = 0 och k = 1

${\displaystyle =\left(F_{0}\cdot x^{0}+F_{1}\cdot x+\sum _{k=2}^{\infty }F_{k}x^{k}\right)-\left(F_{1-1}\cdot x^{1}+\sum _{k=2}^{\infty }F_{k-1}x^{k}\right)-\left(\sum _{k=2}^{\infty }F_{k-2}x^{k}\right)=}$

Slå ihop resterande summor

${\displaystyle =F_{0}+F_{1}\cdot x-F_{0}\cdot x+\sum _{k=2}^{\infty }\left(F_{k}-F_{k-1}-F_{k-2}\right)\cdot x^{k}}$

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

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

Alltså gäller

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

Externa länkar

• archive.org: Genererandefunktioner