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 an, n = 0, 1, 2, ..., definieras som

f ( x ) = ∑ k = 0 ∞ a k x k {\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 an ä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 an, definierad som:

∑ k = 0 ∞ a k k ! x k {\displaystyle \sum _{k=0}^{\infty }{\frac {a_{k}}{k!}}x^{k}} .

Exempel

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

Fn definieras av rekursionen F k + 2 − F k + 1 − F k = 0   {\displaystyle F_{k+2}-F_{k+1}-F_{k}=0\ } , och F 0 = 0 , F 1 = 1   {\displaystyle F_{0}=0,F_{1}=1\ }

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

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

Substituera f(x)

= ( 1 − x − x 2 ) ⋅ ( ∑ k = 0 ∞ F k x k ) = {\displaystyle =(1-x-x^{2})\cdot \left(\sum _{k=0}^{\infty }F_{k}x^{k}\right)=}

Multiplicera in i parentesen

= ∑ k = 0 ∞ F k x k − ∑ k = 0 ∞ F k x k + 1 − ∑ k = 0 ∞ F k x k + 2 = {\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

= ∑ k = 0 ∞ F k x k − ∑ k = 1 ∞ F k − 1 x k − ∑ k = 2 ∞ F k − 2 x k = {\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

= ( F 0 ⋅ x 0 + F 1 ⋅ x + ∑ k = 2 ∞ F k x k ) − ( F 1 − 1 ⋅ x 1 + ∑ k = 2 ∞ F k − 1 x k ) − ( ∑ k = 2 ∞ F k − 2 x k ) = {\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

= F 0 + F 1 ⋅ x − F 0 ⋅ x + ∑ k = 2 ∞ ( F k − F k − 1 − F k − 2 ) ⋅ x k {\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 F0 = 0, F1 = 1 och rekursionen

= 0 + 1 ⋅ x − 0 ⋅ x + ∑ k = 2 ∞ 0 ⋅ x k = x {\displaystyle =0+1\cdot x-0\cdot x+\sum _{k=2}^{\infty }0\cdot x^{k}=x}

Alltså gäller

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

Externa länkar

  • archive.org: Genererandefunktioner