Funció generatriu

En matemàtiques, una funció generadora o funció generatriu és una sèrie formal de potències els coeficients dels quals codifiquen informació sobre una successió a _n en què l'índex corre sobre els enters no negatius.

Hi ha diversos tipus de funcions generadores: funcions generadores ordinàries, funcions generadores exponencials, la sèrie de Lambert, la sèrie de Bell i la sèrie de Dirichlet, de les quals més avall s'ofereixen definicions i exemples. Cada successió té una funció generadora de cert tipus. El tipus de funció generadora, que és apropiada en un context donat, depèn de la naturalesa de la successió i els detalls del problema que s'analitza.

Les funcions generadores són expressions tancades en un argument formal x. De vegades, una funció generadora «s'avalua» en un valor específic x = a, però cal tenir en compte que les funcions generadores són sèries formals de potències, motiu pel qual no es considera ni s'analitza el problema de la convergència en tots els valors de x. Per aquesta raó, és important observar que les funcions generadores no són realment funcions en el sentit usual de ser mapeigs entre un domini i un codomini, el nom és únicament el resultat del desenvolupament històric del seu estudi.

«	Una funció generadora és una corda d'estendre en la qual pengem una successió de nombres per mostrar-la	»
— Herbert Wilf^[1]

Funció generadora ordinària

La funció generadora ordinària d'una successió ( a _n) = a ₀, a ₁, a ₂, a ₃ ... es defineix com

$A(x)=\sum _{n=0}^{\infty }a_{n}x^{n}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots$

És comú usar l'expressió funció generadora sense major qualificatiu, per referir-se a aquest tipus de funció.

Exemple.: la successió de Fibonacci definida per la recurrència

$f_{n+1}=f_{n}+f_{n-1},\quad n>0,\qquad f_{0}=0,f_{1}=1$

és la successió 0,1,1,2,3,5,8,13,21, ...

la seva funció generadora és

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

ja que el desenvolupament en sèrie de potències d'aquesta funció és

${\frac {x}{1-xx^{2}}}=0+1\cdot x+1\cdot x^{2}+2x^{3}+3x^{4}+5x^{5}+8x^{6}+13x^{7}+\cdots$ .

,

i els coeficients de tal desenvolupament són precisament 0,1,1,2,3,5,8,13, ...

És possible definir funcions generadores sobre diverses variables. Per exemple, la funció generadora ordinària en 2 variables de ( a _{m, n}) on n i m són índexs que recorren els enters no negatius, és

$A(x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}=a_{0,0}+a_{1,0}x+a_{0,1}y+a_{2,0}x^{2}+a_{1,1}xy+a_{0,2}y^{2}+a_{3,0}x^{3}+a_{2,1}x^{2}y+\cdots$

Aplicacions

Si bé les funcions generadores són una eina usada àmpliament en combinatòria, no existeixen mètodes detallats que proporcionin solució als problemes en cada situació. No obstant això, existeixen idees generals que poden ser modificades i adaptades a les diferents situacions que es presenten. A continuació, s'il·lustren diversos usos de les funcions generadores juntament amb la idea general que s'està usant.

Determinació de la funció generadora a partir d'una recurrència

En aquesta situació el que es fa és multiplicar banda i banda de la recurrència per x^n i sumar sobre tots els índexs. Després s'efectuen transformacions perquè la igualtat entre sumes que s'obté es converteixi en una equació que involucra la funció generadora i es procedeix a resoldre-la.

Com il·lustració, consideri la recurrència:

$\ a_{n+1}=3a_{n}+2,\qquad a_{0}=1$ .

,

que dona origen a la successió ( a _n) = 1,5,17,53,161,485,1457 ...

Multiplicant ambdós costats per x ⁿ i sumant sobre tots els valors de n s'obté:

$\sum _{n=0}^{\infty }a_{n+1}x^{n}=a_{1}+a_{2}x+a_{3}x^{2}+a_{4}x^{3}+\cdots =\sum _{n=0}^{\infty }(3a_{n}+2)x^{n}$ .

,

El costat esquerre és gairebé la funció generadora, però els índexs estan desfasats. Però notant que

$a_{1}+a_{2}x+a_{3}x^{2}+a_{4}x^{3}+\cdots ={\frac {(a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots )-a_{0}}{x}}$ ,

es dedueix que el costat esquerre és

${\frac {A(x)-a_{0}}{x}}={\frac {A(x)-1}{x}}$ .

,

El costat dret es desenvolupa com

$\sum _{n=0}^{\infty }(3a_{n}+2)x^{n}=3\sum _{k=0}^{\infty }a_{n}x^{n}+2\sum _{k=0}^{\infty }x^{n}=3A(x)+2(1+x+x^{2}+x^{3}+\cdots )=3A(x)+{\frac {2}{1-x}}$ .

,

Al final, es va aplicar la fórmula per sumar una sèrie geomètrica:^[2]

$1+x+x^{2}+x^{3}+x^{4}+\cdots ={\frac {1}{1-x}}$ .

,

Igualant ambdues simplificacions, s'obté l'equació

${\frac {A(x)-1}{x}}=3A(x)+{\frac {2}{1-x}},$

que en resoldre llança per resultat

$A(x)={\frac {x+1}{3x^{2}-4x+1}}.$

Exemple d'aplicació pràctica

Si c _n és el nombre de formes en què es pot pagar n pesos usant monedes d'1, 2 i 5 pesos, llavors la funció generadora de la successió ( c _n ) és

$C(x)={\frac {1}{1-x}}\cdot {\frac {1}{1-x^{2}}}\cdot {\frac {1}{1-x^{5}}}=(1+x+x^{2}+x^{3}+\cdots )(1+x^{2}+x^{4}+x^{6}+\cdots )(1+x^{5}+x^{10}+x^{15}+\cdots )$ .

,

ja que el coeficient de x ⁿ és igual al nombre de formes d'escollir a, b, c tals que

$x^{n}=x^{a}x^{2b}x^{5c}=x^{a+2b+5c},\$

i que corresponen a usar a monedes d'1 pes, b monedes de 2 pesos i c monedes de 5 pesos.

L'aplicació de la fórmula de Taylor és massa complexa en aquest cas, de manera que s'aplica el següent artifici causa de Ronald Graham.

Cada un dels denominadors (1 - x ), (1 - x ²) i (1 - x ⁵) són divisors de (1 - x ¹⁰), pel que podem reescriure:

$C(x)={\frac {A(x)}{(1-x^{10})^{3}}}$

per a un A (x) en què:

${\begin{array}{rcl}A(x)&=&A_{1}(x)\cdot A_{2}(x)\cdot A_{3}(x)=\left({\frac {1-x^{10}}{1-x}}\right)\left({\frac {1-x^{10}}{1-x^{2}}}\right)\left({\frac {1-x^{10}}{1-x^{5}}}\right)\\\ &=&x^{22}+x^{21}+2x^{20}+2x^{19}+3x^{18}+4x^{17}+5x^{16}+6x^{15}+7x^{14}+8x^{13}+7x^{12}+8x^{11}\\\ &\ &\quad +7x^{10}+8x^{9}+7x^{8}+6x^{7}+5x^{6}+4x^{5}+3x^{4}+2x^{3}+2x^{2}+x+1\end{array}}$

Finalment, desenvolupant la funció generadora:

${\frac {1}{(1-x^{10})^{3}}}=\sum _{k\geq 0}{2+k \choose k}x^{10k}={2 \choose 2}+{3 \choose 2}x^{10}+{4 \choose 2}x^{20}+{5 \choose 2}x^{30}+\cdots$

obtenim:

$C(x)=A(x)\sum _{k\geq 0}{2+k \choose k}x^{10k}$ .

De l'expressió anterior es pot llegir amb detall el valor exacte del coeficient de x ⁿ, és a dir, el nombre c _n de formes de pagar n pesos amb monedes d'1,2 i 5 pesos. Per exemple, el nombre de formes de pagar 77 pesos s'obté calculant el terme corresponent x ⁷⁷:

$(6x^{7})\cdot {9 \choose 2}x^{70}+(4x^{17})\cdot {8 \choose 2}x^{60}=\left(6{9 \choose 2}+4{8 \choose 2}\right)x^{77}=(6\cdot 36+4\cdot 28)x^{77}=328x^{77}$

i es conclou que hi ha 328 formes de pagar 77 pesos amb monedes d'1, 2 o 5 pesos.

Altres funcions generadores

Funció generadora exponencial

La funció generadora exponencial d'una successió a _n és:

EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.

Funció generadora de Poisson

La funció generadora de Poisson d'una successió a _nés:

PG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}i^{-x}{\frac {x^{n}}{n!}}.

Sèrie de Lambert

La sèrie de Lambert d'una successió a _nés:

LG(a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.

Nota: en una sèrie de Lambert, l'índex n comença en l'1, no en 0.

Sèrie de Bell

La sèrie de Bell d'una funció aritmètica f (n) i un nombre primer p és:

F_{p}(x)=\sum _{n=0}^{\infty }f(p^{n})x^{n}.

Funció generadora de la sèrie de Dirichlet

Les sèries de Dirichlet sovint es classifiquen com a funcions generadores, encara que no són estrictament sèries formals de potències. La funció generadora de la sèrie de Dirichlet d'una successió a _nés:

DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.

La funció generadora de la sèrie de Dirichlet és especialment útil quan a _nés una funció multiplicativa, quan té una expressió de producte d'Euler en termes de la sèrie de Bell de la funció:

DG(a_{n};s)=\prod _{p}f_{p}(p^{-s})\,.

Si a_nés un caràcter de Dirichlet, llavors la seva funció generadora de la sèrie de Dirichlet es diu sèrie L de Dirichlet.

Funcions generadores de successions polinòmiques

El concepte de funcions generadores pot estendre a successions d'altres objectes. Així, per exemple, les successions polinòmiques de tipus binomial es generen per:

I^{xf(t)}=\sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n}

en què p_n(x) és una successió de polinomis i f (t) és una funció de certa manera. Les successions de Sheffer es generen de manera similar. Vegeu l'article principal polinomi generalitzat de Appell per a més informació.

Exemples

Quan es treballa amb funcions generadores, és important reconèixer les expressions d'algunes successions fonamentals.

Funcions generadores ordinàries

La més fonamental de totes és la successió constant 1,1,1,1, ..., la funció generadora ordinària és:

\sum _{n\in \mathbf {N} }X^{n}={1 \over 1-X}.

L'expressió de la dreta es pot justificar multiplicant la sèrie de potències de l'esquerra per $X-1$ , i comprovant que el seu resultat sigui la sèrie constant de potències 1. En altres paraules, que tots els coeficients desapareguin excepte el de X ⁰. (D'altra banda, no hi pot haver una altra sèrie de potències amb aquesta propietat, ja que un anell de sèries de potències com Z ''X'' és un domini d'integritat.) El costat de la dreta, per tant, designa la inversa de $X-1$ en l'anell de sèries de potències.

Fàcilment es deriva, mitjançant aquestes expressions, la generació ordinària d'altres successions. Per exemple, per a la sèrie geomètrica 1, a , a ², a ³,... per a cada constant a s'ha:

\sum _{n\in \mathbf {N} }a^{n}x^{n}={1 \over 1-aX},

i en particular:

\sum _{n\in \mathbf {N} }(-1)^{n}x^{n}={1 \over 1+X}.

També es poden introduir «bretxes» regulars en la successió substituint X per alguna potència de X, així, per exemple, per a la sucesió 1, 0,1, 0,1,0,1,0, .... s'obté la funció generadora:

\sum _{n\in \mathbf {N} }X^{2n}={1 \over 1-X^{2}}.

Calculant el quadrat de la funció generadora inicial, fàcilment es veu que els coeficients formen la successió 1, 2, 3, 4, 5, ..., així que s'ha:

\sum _{n\in \mathbf {N} }(n+1)X^{n}={1 \over (1-X)^{2}},

i el cub té com a coeficients els nombres triangulars 1,3,6,10,15,21, ... el terme n és el coeficient binomial ${\tbinom {n+2}{2}}$ , de manera que

\sum _{n\in \mathbf {N} }{\tbinom {n+2}{2}}X^{n}={1 \over (1-X)^{3}}.

Atès que ${\tbinom {n+2}{2}}={\frac {1}{2}}{(n+1)(n+2)}={\frac {1}{2}}(n^{2}+3n+2)$ , es pot trobar la funció generadora ordinària per a la successió 0, 1, 4, 9, 16, ... de nombres quadrats per combinació lineal de les successions precedents;

Funció generadora exponencial

EG(n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)i^{x}

Sèrie de Bell

F_{p}(x)=\sum _{n=0}^{\infty }p^{2n}x^{n}={\frac {1}{1-p^{2}x}}

Funció generadora de la sèrie de Dirichlet

DG(n^{2};s)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2)

Aplicacions

Les funcions generadores s'empren per:

Trobar una forma tancada per a una successió donada en una relació de recurrència. Per exemple, considereu els nombres de Fibonacci.
Trobar relacions de recurrència per successions: la forma d'una funció generadora pot suggerir una fórmula de recurrència.
Trobar relacions entre successions: si les funcions generadores de dues successions tenen una forma similar, llavors les mateixes successions probablement estan relacionades.
Explorar el comportament asimptòtic de les successions.
Demostrar identitats que impliquen successions.
Resoldre problemes d'enumeració a combinatòria.
Avaluar sumes infinites.

Altres funcions generadores

Exemples de successions polinòmiques generades per funcions generadores complexes són:

Vegeu també

Referències

Herbert S. Wilf, 7Ewilf/DownldGF.html Generatingfunctionology (Second Edition)^{[Enllaç no actiu]} (1994) Academic Press. ISBN 0-12-751956-4.
Donald E. Knuth, The Art of Computer Programming, Volume 1 Fonamental Algorithms (Third Edition) Addison-Wesley. ISBN 0-201-89683-4. Section 1.2.9: Generating Functions, pp. 87–96.
Ronald L. Graham, Donald E. Knuth, i Oren Patashnik, Concrete Mathematics. A foundation for computer science (Second Edition) Addison-Wesley. ISBN 0-201-55802-5. Chapter 7: Generating Functions, pàg. 320-380.
Gabriel Poveda Ramos, Funcions generatrius , Editorial de la Universitat Pontifícia Bolivariana, ISBN 958-696-539-2, 90 pp., Medellín (Colòmbia) 2006.

Notes

↑ Wilf, Herbert. generatingfunctionology. 2a ed.. A. K. Peters, 1994. ISBN 978-1-56881-279-3.
↑ Com es va esmentar en la introducció, realment no importa el radi de convergència d'una sèrie, ja que només es busca manipular formalment (és a dir, «mecànicament») les expressions. En general és suficient que una sèrie sigui convergent en un disc obert (no determinat) al voltant de zero per poder usar-la. En l'exemple, la sèrie geomètrica és convergent en el disc -1 < x <1.

Enllaços externs

Funcions generadores, índexs de potències i canvi de moneda en Cut-the-knot.org (consultat l'1 d'agost de 2008) (anglès)
Versió descarregable en anglès de Generatingfunctionology, d'H Wilf (consultat l'1 d'agost de 2008)
1031 Generating Functions (consultat l'1 d'agost de 2008)
"Generating Functions" per Ed Pegg, Jr, en el lloc web The Wolfram Demonstrations Project, 2007. (Consultat l'1 d'agost de 2008)

[1] Wilf, Herbert. generatingfunctionology. 2a ed.. A. K. Peters, 1994. ISBN 978-1-56881-279-3.

[2] Com es va esmentar en la introducció, realment no importa el radi de convergència d'una sèrie, ja que només es busca manipular formalment (és a dir, «mecànicament») les expressions. En general és suficient que una sèrie sigui convergent en un disc obert (no determinat) al voltant de zero per poder usar-la. En l'exemple, la sèrie geomètrica és convergent en el disc -1 < x <1.

[1]

[2]