Vés al contingut

Funció generatriu

De la Viquipèdia, l'enciclopèdia lliure

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

[modifica]

La funció generadora ordinària d'una successió ( a n ) = a 0 , a 1 , a 2 , a 3 ... es defineix com

É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

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

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

.

,
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

Aplicacions

[modifica]

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

[modifica]

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:

.

,

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

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

.

,

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

,

es dedueix que el costat esquerre és

.

,

El costat dret es desenvolupa com

.

,

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

.

,

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

que en resoldre llança per resultat

Exemple d'aplicació pràctica

[modifica]

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

.

,

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

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 2 ) i (1 - x 5 ) són divisors de (1 - x 10 ), pel que podem reescriure:

per a un A (x) en què:

Finalment, desenvolupant la funció generadora:

obtenim:

.

De l'expressió anterior es pot llegir amb detall el valor exacte del coeficient de x n , é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 77 :

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

Altres funcions generadores

[modifica]

Funció generadora exponencial

[modifica]

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

Funció generadora de Poisson

[modifica]

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

Sèrie de Lambert

[modifica]

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

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

Sèrie de Bell

[modifica]

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

Funció generadora de la sèrie de Dirichlet

[modifica]

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:

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ó:

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

[modifica]

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:

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

[modifica]

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

Funcions generadores ordinàries

[modifica]

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

L'expressió de la dreta es pot justificar multiplicant la sèrie de potències de l'esquerra per , 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 0. (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 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 2 , a 3 ,... per a cada constant a s'ha:

i en particular:

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:

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:

i el cub té com a coeficients els nombres triangulars 1,3,6,10,15,21, ... el terme n és el coeficient binomial , de manera que

Atès que , 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

[modifica]

Sèrie de Bell

[modifica]

Funció generadora de la sèrie de Dirichlet

[modifica]

Aplicacions

[modifica]

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

[modifica]

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

Vegeu també

[modifica]

Referències

[modifica]

Notes

[modifica]
  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.

Enllaços externs

[modifica]