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

m
Corregit: - </math>.}} ja + </math>.}}, ja
m (Corregit: - problemes de enumeració + problemes d'enumeració)
m (Corregit: - </math>.}} ja + </math>.}}, ja)
{{Equació|<math> F (x) = \frac{x}{1-x-x^2}</math>}}
: Ja 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>.}},
: I els coeficients de tal desenvolupament són precisament 0,1,1,2,3,5,8,13, ...
</Div>
<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óna 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é:
{{Equació|<math> \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 </math>.}},
 
El costat esquerre és '' gairebé '' la funció generadora, però els índexs estan desfasats. Però notant que
{{Equació|<math> 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}</math>,}}
es dedueix que el costat esquerre és
{{Equació|<math> \frac{A (x)-a_0}{x}= \frac{A (x) -1}{x}</math>.}},
 
El costat dret es desenvolupa com
{{Equació|<math> \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}</math>.}},
 
Al final, es va aplicar la fórmula per sumar una sèrie geomètrica:<ref>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 (matemàtica)|disc]] [[conjunt obert|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.</ref>
{{Equació|<math> 1+x+x^2+x^3+x^4+\cdots = \frac{1}{1-x}</math>.}},
 
Igualant ambdues simplificacions, s'obté l'equació
=== 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>}}
{{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>:
1.130.230

modificacions