Diferència entre revisions de la pàgina «Funció generatriu»

cap resum d'edició
m (Aplicant la plantilla {{ISBN}} per evitar l'enllaç màgic d'ISBN)
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ó matemàtica|successió]] '' a '' <sub> '' n '' </sub> en què l'índex corre sobre els [[nombres naturals|enters no negatius]].
{{2L|data=febrer de 2013}}
En [[matemàtiques]], una '''funció generadora''' o '''funció generatriu''' és una [[sèrie formal de potències]] els coeficients codifiquen informació sobre una [[Successió matemàtica|successió]] '' a '' <sub> '' n '' </sub> l'índex corre sobre els [[nombres naturals|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 baixmé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 [[forma tancada (matemàtica)|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 quequal no es considera ni s'analitza el problema de la [[convergència (matemàtiques)|convergència]] en tots els valors de '' x. ''Per aquesta raó, és important observar que les funcions generadores'' no'' són realment [[funció matemàtica|funcions]] en el sentit usual de ser [[mapeig]]s entre un [[domini de definició|domini]] i un [[codomini]], el nom és únicament el resultat del desenvolupament històric del seu estudi.{{Cita|''Una funció generadora és una corda d'estendre en la qual pengem una successió de nombres per mostrar-la''|[[Herbert Wilf]]<ref>{{ref-llibre|cognom = Wilf|nom = Herbert|enllaçautor = Herbert Wilf|edició =2a ed.|títol = generatingfunctionology|any = 1994| editorial = A. K. Peters|isbn = 978-1-56881-279-3}}</ref>}}
 
Pel mateix és important observar que les funcions generadores '' no '' són realment [[funció matemàtica|funcions]] en el sentit usual de ser [[mapeig]]s entre un [[domini de definició|domini]] i un [[codomini]], el nom és únicament el resultat del desenvolupament històric del seu estudi.
{{Cita|''Una funció generadora és una corda d'estendre en la qual pengem una successió de nombres per mostrar-la''|[[Herbert Wilf]]<ref>{{ref-llibre|cognom = Wilf|nom = Herbert|enllaçautor = Herbert Wilf|edició =2a ed.|títol = generatingfunctionology|any = 1994| editorial = A. K. Peters|isbn = 978-1-56881-279-3}}</ref>}}
 
== Funció generadora ordinària ==
 
La '' funció generadora ordinària '' d'una successió ('' a '' <sub> '' n '' </sub>) = '' a '' <sub> 0 </sub>, '' a '' <sub> 1 </sub>, '' a '' <sub> 2 </sub>, '' a '' <sub> 3 </sub> ... es defineix com
{{Equació|<math> A (x) = \sum_{n = 0}^{\infty}a_nx^n = a_0+a_1x+a_2x^2+a_3x^3+\cdots </math>}}
És comú usar l'expressió '' funció generadora '' sense major qualificatiu, per referir-se a aquest tipus de funció.
 
<div style="padding:5px; background-color:#FCFCFC; border:1px solid #Aaa; margin-left:5em; margin-right:2em;">
; Exemple.
: Lala successió de Fibonacci definida per la recurrència
{{Equació|<math> f_{n+1}= f_{n}+f_{n-1}, \quad n> 0, \qquad f_0 = 0, f_1 = 1 </math>}}
: Ésés la successió ''' 0,1,1,2,3,5,8,13,21, ... '''
 
: Lala seva funció generadora és
{{Equació|<math> F (x) = \frac{x}{1-x-x^2}</math>}}
: Jaja que el desenvolupament en sèrie de potències d'aquesta funció és
{{Equació|<math> \frac{x}{1-xx^2}= 0+1 \cdot x+1 \cdot x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots </math>.}},
 
: Ii els coeficients de tal desenvolupament són precisament 0,1,1,2,3,5,8,13, ...
</Div>
És possible definir funcions generadores sobre diverses variables. Per exemple, la funció generadora ordinària en 2 variables de ('' a '' <sub> '' m, n '' </sub>) on '' n '' i '' m '' són índexs que recorren els enters no negatius, és
 
== Aplicacions ==
Si bé les funcions generadores són una eina usada àmpliament en combinatòriacombinació, 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 ===
 
<div style="padding:5px; background-color:#FCFCFC; border:1px solid #Aaa; margin-left:5em; margin-right:2em;">
Com il·lustració, consideri la recurrència:
{{Equació|<math> \ a_{n+1}= 3a_n+2, \qquad a_0 = 1 </math>.}},
que dónadona origen a la successió ('' a '' <sub> '' n '' </sub>) = 1,5,17,53,161,485,1457 ...
 
Multiplicant ambdós costats per '' x '' <sup> '' n '' </sup> i sumant sobre tots els valors de '' n '' s'obté:
 
=== Exemple d'aplicació pràctica ===
Si '' c <sub> n </sub> '' é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 <sub> n </sub> '') és
{{Equació|<math> 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) </math>.}},
ja que el coeficient de '' x <sup> n </sup> '' és igual al nombre de formes d'escollir '' a '', '' b '', '' c '' tals que
{{Equació|<math> x^n = x^ax^{2b}x^{5c}= x^{a+2b+5c}, \ </math>}}
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 aplicarems'aplica el següent artifici causa de [[Ronald Graham]].
 
Cada un dels denominadors (1 - '' x ''), (1 - '' x '' <sup> 2 </sup>) i (1 - '' x '' <sup> 5 </sup>) són divisors de (1 - '' x '' <sup> 10 </sup>), pel que podem reescriure:
{{Equació|<math> C (x) = \frac{A (x)}{(1-x^{10})^3}</math>}}
per a un '' A '' ('' x )'') onen què:
{{Equació |<math>\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}</math>}}
 
Finalment, desenvolupant la funció generadora:
{{Equació|1 = <math> \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 </math>}}
obtenim:
{{Equació|<math> C (x) = A (x) \sum_{k \ge0}{2+k \choose k}x^{10k}</math>.}},
 
De l'expressió anterior es pot llegir amb detall el valor exacte del coeficient de '' x '' <sup> '' n '' </sup>, és a dir, el nombre '' c '' <sub> '' n '' </sub> 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 '' <sup> 77 </sup>:
{{Equació|<math> (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}</math>}}
i es conclou que hi ha 328 formes de pagar 77 pesos amb monedes d'1, 2 o 5 pesos.
=== Funció generadora exponencial ===
 
La '' funció generadora exponencial '' d'una successió '' a '' <sub> '' n '' </sub> és:
 
: <math> EG (a_n; x) = \sum _{n = 0}^{\infty}a_n \frac{x^n}{n !}. </math>
=== Funció generadora de Poisson ===
 
La '' funció generadora de [[Poisson]] '' d'una successió '' a '' <sub> '' n '' </sub> és:
 
: <math> PG (a_n; x) = \sum _{n = 0}^{\infty}a_n i^{-x}\frac{x^n}{n !}. </math>
=== Sèrie de Lambert ===
 
La '' [[sèrie de Lambert]] '' d'una successió '' a '' <sub> '' n '' </sub> és:
 
: <math> LG (a_n; x) = \sum _{n = 1}^{\infty}a_n \frac{x^n}{1-x^n}. </math>
 
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:
 
: <math> F_p (x) = \sum_{n = 0}^\infty f (p^n) x^n. </math>
=== Funció generadora de la sèrie de Dirichlet ===
 
Les [[sèrie de Dirichlet|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 '' <sub> '' n '' </sub> és:
 
: <math> DG (a_n; s) = \sum _{n = 1}^{\infty}\frac{a_n}{n^s}. </math>
 
La funció generadora de la sèrie de Dirichlet és especialment útil quan '' a '' <sub> '' n '' </sub> és una [[funció multiplicativa]], quan té una expressió de [[producte d'Euler]] en termes de la sèrie de Bell de la funció:
 
: <math> DG (a_n; s) = \prod_{p}f_p (p^{-s}) \,. </math>
 
Si '' a '' <sub> '' n '' </sub> és un [[caràcter de Dirichlet]], llavors la seva funció generadora de la sèrie de Dirichlet es diu [[funció L de Dirichlet|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:
 
: <math> I^{xf (t)}= \sum_{n = 0}^\infty{p_n (x) \over n !}t^n </math>
 
onen què '' p '' <sub> '' n '' </sub> ('' x '') és una successió de polinomis i '' f '' ('' t '') és una funció de certa manera. Les [[Successió de Sheffer|successions de Sheffer]] es generen de manera similar. Vegeu l'article principal [[polinomi generalitzat de Appell]] per a més informació.
 
== Exemples ==
=== Funcions generadores ordinàries ===
 
La més fonamental de totes és la successió constant 1,1,1,1, ..., la funció generadora ordinària és:
: <math> \sum_{n \in \mathbf{N}}X^n ={1 \over1-X}. </math>
L'expressió de la dreta es pot justificar multiplicant la sèrie de potències de l'esquerra per <math> X-1 </math>, i comprovant que el seu resultat sigui la sèrie constant de potències 1;. enEn altres paraules, que tots els coeficients desapareguin excepte el de '' X '' <sup> 0 </sup>. (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 ''|<nowiki>''X''</nowiki>]] és un [[domini d'integritat]].) El costat de la dreta, per tant, designa la inversa de <math> X-1 </math> en l'anell de sèries de potències.
 
Fàcilment es derivenderiva, permitjançant aquestaaquestes expressions per a, la generació ordinària d'altres successions. Per exemple, per a la [[sèrie geomètrica]]
1, '' a '', '' a '' <sup> 2 </sup>, '' a '' <sup> 3 </sup>, ... per a cada constant '' a '' s'ha:
: <math> \sum_{n \in \mathbf{N}}a^nx^n ={1 \over1-aX}, </math>
 
i en particular:
: <math> \sum_{n \in \mathbf{N}}(-1)^nx^n ={1 \over1+X}. </math>
També es poden introduir «bretxes» regulars en la successió substituint '' X '' per alguna potència de '' X '', així, per exemple, per a la sucesión1sucesió 1, 0,1, 0,1,0,1,0, .... s'obté la funció generadora:
: <math> \sum_{n \in \mathbf{N}}X^{2n}={1 \over1-X^2}. </math>
Calculant el [[quadrat (aritmètica)|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:
: <math> \sum_{n \in \mathbf{N}}(n+1) X^n ={1 \over (1-X)^2}, </math>
i el [[cub (aritmètica)|cub]] té com a coeficients els [[nombre triangular|nombres triangulars]] 1,3,6,10,15,21, ... el terme '' n '' és el [[coeficient binomial]] <math> \tbinom{n+2}2 </math>, de manera que
: <math> \sum_{n \in \mathbf{N}}\tbinom{n+2}2 X^n ={1 \over (1-X)^3}. </math>
Atès que <math> \tbinom{n+2}2 = \frac12{(n+1) (n+2)}= \frac12 (n^2+3n+2) </math>, es pot trobar la funció generadora ordinària per a la successió 0, 1, 4, 9, 16, ... de [[quadrat (aritmètica)|nombres quadrats]] per combinació lineal de les successions precedents;
 
=== Funció generadora exponencial ===
== Aplicacions ==
 
Les funcions generadores s'empren per:
 
* Trobar una [[forma tancada (matemàtica)|forma tancada]] per a una successió donada en una relació de recurrència. Per exemple, considereu els [[Successió de Fibonacci|nombres de Fibonacci]];.
* Trobar [[relació de recurrència|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.
 
336

modificacions