Funció generatriu

De Viquipèdia
Dreceres ràpides: navegació, cerca

En matemàtiques, una funció generadora o funció generatriu és una sèrie formal de potències els coeficients codifiquen informació sobre una successió a n 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 baix 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, pel que no es considera ni s'analitza el problema de la convergència en tots els valors de x .

Pel mateix és important observar que les funcions generadores no són realment funcions en 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 | modifica el codi]

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

 A (x) = \sum_{n = 0}^{\infty}a_nx^n = a_0+a_1x+a_2x^2+a_3x^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^my^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^2y + \cdots

Aplicacions[modifica | modifica el codi]

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 | modifica el codi]

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 dóna 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é:

 \sum_{n = 0}^\infty a_{n+1}x^n = a_1+a_2x+a_3x^2+a_4x^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_2x+a_3x^2+a_4x^3+\cdots = \frac{(a_0+a_1x+a_2x^2+a_3x^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_nx^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}= 3 A (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[modifica | modifica el codi]

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 n és igual al nombre de formes d'escollir a , b , c tals que

 x^n = x^ax^{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 aplicarem 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

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

per a un A ( x ) on:

\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 \ge0}{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 \ge0}{2+k \choose k}x^{10k}.

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 :

 (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[modifica | modifica el codi]

Funció generadora exponencial[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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

on 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 més informació.

Exemples[modifica | modifica el codi]

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

Funcions generadores ordinàries[modifica | modifica el codi]

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 \over1-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 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  X-1 en l'anell de sèries de potències.

Fàcilment es deriven per aquesta expressions per a 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

 \sum_{n \in \mathbf{N}}a^nx^n ={1 \over1-aX},

i en particular

 \sum_{n \in \mathbf{N}}(-1)^nx^n ={1 \over1+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ón1, 0,1,0,1,0,1,0, .... s'obté la funció generadora

 \sum_{n \in \mathbf{N}}X^{2n}={1 \over1-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 = \frac12{(n+1) (n+2)}= \frac12 (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[modifica | modifica el codi]

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

Sèrie de Bell[modifica | modifica el codi]

 F_p (x) = \sum_{n = 0}^\infty p^{2n}x^n = \frac{1}{1-p^2x}

Funció generadora de la sèrie de Dirichlet[modifica | modifica el codi]

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

Aplicacions[modifica | modifica el codi]

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 pròpies successions probablement estan relacionades;
  • Explorar el comportament asimptòtic de les successions;
  • Demostrar identitats que impliquen successions;
  • Resoldre problemes de enumeració a combinatòria;
  • Avaluar sumes infinites.

Altres funcions generadores[modifica | modifica el codi]

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

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

Notes[modifica | modifica el codi]

  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 | modifica el codi]