Ver o código fonte de «Función xeradora»

En [[matemáticas]], unha '''función xeradora''' é unha representación dunha [[Sucesión (matemáticas)|secuencia infinita]] de números como os [[Coeficiente|coeficientes]] dunha [[serie formal de potencias]]. As funcións xeradoras adoitan expresarse en [[forma pechada]] (máis que como unha serie), mediante algunha expresión que implique operacións sobre a serie formal.

Existen varios tipos de funcións xeradoras, incluíndo '''funcións xeradoras ordinarias''', '''funcións xeradoras exponenciais''', '''series de Lambert''', '''series de Bell''' e '''series de Dirichlet'''. Cada secuencia en principio ten unha función xeradora de cada tipo (excepto que as series de Lambert e Dirichlet requiren que os índices comecen en 1 en lugar de 0), mais a facilidade coa que se poden manexar pode diferir considerablemente. A función  xeradora particular, se é o caso, que sexa máis útil nun contexto dado dependerá da natureza da secuencia e dos detalles do problema que se trate.

== Definición e nomenclatura ==
A seguinte definición está dada por [[George Pólya]] en  ''[[Mathematics and plausible reasoning]]'' (1954):

"Unha función xeradora é un dispositivo algo parecido a unha bolsa. En lugar de levar moitos pequenos obxectos separados, o que pode ser vergoñento, poñémolos todos nunha bolsa, e despois só temos un obxecto para levar, a bolsa."

Unha '''función xeradora ordinaria''' tería a forma <math>f(x) = a_0 + a_1 x + a_2 x^2 + \cdots </math> onde <math>a_0,  a_1,  a_2, \cdots </math> son os termos da secuencia a considerar. Resulta útil e frecuente representar a función xeradora mediante unha [[forma pechada]].

'''Exemplo:'''  Para a secuencia: <math>1,  3,  9, 27, \cdots </math> temos a función xeradora ordinaria <math>f(x) = 1 + 3 x + 9 x^2 + 27 x^3 +\cdots </math>. Podemos obter unha forma pechada usando a [[serie xeométrica]], <math>f(x) = \dfrac{1}{1-3x} </math>.
Se atendemos a esa igualdade como unha función normal só se cumpriría para valores de {{Mvar|x}} menores a <math>3/4 </math> mais podemos usala como unha serie formal de potencias e aplicar as transformacións explicadas a continuación e que permiten resolver problemas sobre secuencias.

Para refererirse ao elemento <math>a_n</math> dunha serie formal de potencias  <math>f(x)</math> úsase a potencia de {{Mvar|x}} fechada entre corchetes. Así <math>[x^n] f(x)</math> quere dicir "o coeficiente de <math>x^n</math> na función <math>f(x)</math>.<ref>{{Cita libro|título=generatingfunctionology|url=https://archive.org/details/generatingfuncti0000wilf|apelidos=Wilf|nome=Herbert S.|editorial=Academic Press, Inc|ano=1990}}</ref>

Por exemplo:
:<math>[x^n]e^x=1/n!; \quad [u^m](1+u)^s = \binom{s}{m}</math>.

=== Converxencia ===
A diferenza dunha serie ordinaria, a serie formal de potencias non está obrigada a [[Serie converxente|converxer]]: de feito, a función xeradora non se considera realmente unha [[función]] e a "variábel" segue a ser unha indeterminada. Pódese xeneralizar a series de potencias formais en máis dunha indeterminada, para codificar información sobre matrices multidimensionais infinitas de números. Así as funcións xeradoras non son funcións no sentido formal dunha asignación dun [[Dominio de definición|dominio]] a un [[codominio]].

=== Limitacións ===
Non todas as expresións que teñen significado como funcións de&nbsp;{{Mvar|x}} son significativas como expresións que designan series formais; por exemplo, as potencias negativas ou de fracción de&nbsp;{{Mvar|x}} son exemplos de funcións que non teñen unha serie formal de potencias correspondente.

== Tipos ==

=== Función xeradora ordinaria (OGF) ===
Cando se usa o termo ''función xeradora'' sen cualificación, adoita considerarse unha función xeradora ordinaria. A ''función xeradora ordinaria'' dunha secuencia {{Math|''a''<sub>''n''</sub>}} é: 
: <math>G(a_n;x)=\sum_{n=0}^\infty a_n x^n.</math>
Se {{Math|''a''<sub>''n''</sub>}} é a [[Función masa de probabilidade|función de masa de probabilidade]] dunha [[Variable aleatoria|variábel aleatoria discreta]], entón a súa función xeradora ordinaria chámase [[Función xeradora de probabilidades|función xeradora de probabilidade]].

=== Función xeradora exponencial (EGF) ===
A ''función xeradora exponencial'' dunha secuencia {{Math|''a''<sub>''n''</sub>}} é 
: <math>\operatorname{EG}(a_n;x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}.</math>

As funcións xeradoras exponenciais son xeralmente máis convenientes que as funcións xeradoras ordinarias para problemas de [[combinatoria enumerativa]] que impliquen obxectos etiquetados.<ref>{{Cita Harvard sen parénteses|Flajolet|Sedgewick|2009|p=95}}</ref>

=== Función xeradora de Poisson ===
A ''función xeradora de Poisson'' dunha secuencia {{Math|''a''<sub>''n''</sub>}} é 
:<math>\operatorname{PG}(a_n;x)=\sum _{n=0}^\infty a_n e^{-x} \frac{x^n}{n!} = e^{-x}\, \operatorname{EG}(a_n;x).</math>

=== Serie de Lambert ===
A ''serie de Lambert'' dunha sucesión {{Math|''a''<sub>''n''</sub>}} é 
:<math>\operatorname{LG}(a_n;x)=\sum _{n=1}^\infty a_n \frac{x^n}{1-x^n}.</math>
Teña en conta que nunha serie de Lambert o índice {{Mvar|n}} comeza en 1, non en 0, xa que o primeiro termo estaría sen definir.

Os coeficientes da serie de Lambert nas expansións en serie de potencias 
: <math>b_n := [x^n] \operatorname{LG}(a_n;x)</math>
para os enteiros {{Math|''n'' ≥ 1}} están relacionados pola suma dos divisores 
: <math>b_n = \sum_{d|n} a_d.</math> 
Onde <math>[x^n]</math> é o coeficiente da potencia <math>x^n</math> como vimos na notación.

=== Serie de Bell ===
A [[Serie Bell|serie de Bell]] dunha sucesión {{Math|''a''<sub>''n''</sub>}} é unha expresión en termos tanto dunha {{Mvar|x}} indeterminada como dun {{Mvar|p}} primo e vén dada por: 
: <math>\operatorname{BG}_p(a_n;x) = \sum_{n=0}^\infty a_{p^n}x^n.</math>

=== Funcións xeradoras de series de Dirichlet (DGF) ===
[[Serie formal de Dirichlet|As series formais de Dirichlet]] adoitan clasificarse como funcións xeradoras, aínda que non son series formais de potencias en sentido estrito. A ''función xeradora da serie de Dirichlet'' dunha secuencia {{Math|''a''<sub>''n''</sub>}} é: <ref name="W56">{{Cita Harvard sen parénteses|Wilf|1994|p=56}}</ref> 
: <math>\operatorname{DG}(a_n;s)=\sum _{n=1}^\infty \frac{a_n}{n^s}.</math>

A función xeradora en serie de Dirichlet é especialmente útil cando {{Math|''a''<sub>''n''</sub>}} é unha [[función multiplicativa]], nese caso ten unha expresión como [[Produto Euler|produto de Euler]] <ref name="W59">{{Cita Harvard sen parénteses|Wilf|1994|p=59}}</ref> en termos da serie de Bell da función: 
: <math>\operatorname{DG}(a_n;s)=\prod_{p} \operatorname{BG}_p(a_n;p^{-s})\,.</math>

=== Funcións xeradoras de secuencias polinómicas ===
A idea de funcións xeradora pódese estender a secuencias doutros obxectos. Así, por exemplo, as secuencias polinómicas de tipo binomial son xeradas por: 
: <math>e^{xf(t)}=\sum_{n=0}^\infty \frac{p_n(x)}{n!} t^n</math>
onde {{Math|''p''<sub>''n''</sub>(''x'')}} é unha secuencia de polinomios e {{Math|''f''(''t'')}} é unha función dunha determinada forma. [[Secuencias de Sheffer|As secuencias de Sheffer]] xéranse dun xeito similar. Consulte o artigo principal sobre  [[polinomios de Appell xeneralizados]] para obter máis información.

Exemplos de [[Secuencia polinómica|secuencias polinómicas]] xeradas por funcións xeradoras máis complexas inclúen:

* [[Polinomios de Appell]]
* [[Polinomios de Chebyshev]]
* [[Polinomios por diferenzas]]
* [[Polinomios de Appell xeneralizados]]
* [[Polinomio por q-diferenzas|Polinomios por {{Mvar|q}}-diferenzas]]

== Funcións xeradoras ordinarias ==

=== Exemplos de secuencias sinxelas ===
Unha función xeradora fundamental é a da secuencia constante {{Nowrap|1, 1, 1, 1, 1, 1, 1, 1, 1, ...}} , cuxa función xeradora ordinaria é a [[serie xeométrica]] 
:<math>\sum_{n=0}^\infty x^n= \frac{1}{1-x}.</math>

O lado esquerdo é a expansión da [[Serie de Taylor|serie de Maclaurin]] do lado dereito. 

As expresións para a función xeradora ordinaria doutras secuencias derívanse facilmente desta. Por exemplo, a substitución {{Math|''x'' → ''ax''}} dá a función xeradora para a [[Progresión xeométrica|secuencia xeométrica]] {{Math|1, ''a'', ''a''<sup>2</sup>, ''a''<sup>3</sup>, ...}} para calquera constante {{Mvar|a}}
: <math>\sum_{n=0}^\infty(ax)^n= \frac{1}{1-ax}.</math>

(A igualdade tamén se deduce directamente do feito de que o lado esquerdo é a expansión da serie de Maclaurin do lado dereito.) En particular,
: <math>\sum_{n=0}^\infty(-1)^nx^n= \frac{1}{1+x}.</math>

Tamén se poden introducir ocos regulares na secuencia substituíndo {{Mvar|x}} por algunha potencia de {{Mvar|x}}, así, por exemplo, para a secuencia {{Nowrap|1, 0, 1, 0, 1, 0, 1, 0, ...}} (que salta sobre {{Math|''x'', ''x''<sup>3</sup>, ''x''<sup>5</sup>, ...}} ) obtense a función xeradora 
: <math>\sum_{n=0}^\infty x^{2n} = \frac{1}{1-x^2}.</math>

Ao elevar ao cadrado a función xeradora inicial, ou achar a derivada de ambos os dous lados con respecto a {{Mvar|x}} e facer un cambio da variábel  {{Math|''n'' → ''n'' + 1}}, vese que os coeficientes forman a secuencia {{Nowrap|1, 2, 3, 4, 5, ...}} , así un ten 
: <math>\sum_{n=0}^\infty(n+1)x^n= \frac{1}{(1-x)^2},</math>

e a terceira potencia ten como coeficientes os [[Número triangular|números triangulares]] {{Nowrap|1, 3, 6, 10, 15, 21, ...}} cuxo termo {{Mvar|n}} é o [[coeficiente binomial]] <math>\binom{n+2}{2}</math>, de xeito que 
: <math>\sum_{n=0}^\infty\binom{n+2}2 x^n= \frac{1}{(1-x)^3}.</math>

Por indución, podemos mostrar de xeito similar para os enteiros positivos {{Math|''m'' ≥ 1}} que<ref>{{cita publicación periódica|first1= Michael Z. | last1=Spivey | title=Combinatorial Sums and Finite Differences | year=2007 |journal = Discrete Math. |doi = 10.1016/j.disc.2007.03.052 | volume=307|number=24|pages=3130–3146|mr=2370116}}</ref><ref>{{cite arXiv|first1=R. J. |last1=Mathar|year=2012|eprint=1207.5845|title=Yet another table of integrals|class=math.CA}}</ref>
: <math>n^m = \sum_{j=0}^m \begin{Bmatrix} m \\ j \end{Bmatrix} \frac{n!}{(n-j)!}, </math>

onde {{Math|{{resize|150%|{}}{{su|p=''n''|b=''k''}}{{resize|150%|}<nowiki/>}}}} denota os [[números de Stirling do segundo tipo]] e onde temos a función xeradora 
: <math>\sum_{n = 0}^\infty \frac{n!}{ (n-j)!} \, z^n = \frac{j! \cdot z^j}{(1-z)^{j+1}},</math>

de xeito que podemos formar as funcións xeradoras análogas sobre as potencias enteiras {{Mvar|m}}-ésimas xeneralizando o resultado no caso do cadrado anterior. En particular, xa que podemos escribir 
: <math>\frac{z^k}{(1-z)^{k+1}} = \sum_{i=0}^k \binom{k}{i} \frac{(-1)^{k-i}}{(1-z)^{i+1}},</math>

podemos aplicar unha coñecida identidade de suma finita que inclúe os [[números de Stirling]] para obter que <ref>{{Cita Harvard sen parénteses|Graham|Knuth|Patashnik|1994}} for finite sum identities involving the Stirling number triangles.</ref> 
:<math>\sum_{n = 0}^\infty n^m z^n = \sum_{j=0}^m \begin{Bmatrix} m+1 \\ j+1 \end{Bmatrix} \frac{(-1)^{m-j} j!}{(1-z)^{j+1}}. </math>

=== Funcións racionais ===
A función xeradora ordinaria dunha secuencia pódese expresar como unha [[función racional]] (a razón de dous polinomios de grao finito) se e só se a secuencia é unha [[Secuencia lineal recursiva|secuencia linear recursiva]] con coeficientes constantes. E viceversa, toda secuencia xerada por unha fracción de polinomios satisfai unha recorrencia linear con coeficientes constantes. Esta observación mostra que é fácil de resolver por funcións xeradoras as secuencias definidas por unha [[Ecuación de diferenzas finitas|ecuación linear de diferenzas finitas]] con coeficientes constantes. O exemplo prototípico aquí é derivar [[Sucesión de Fibonacci|a fórmula de Binet]] para os [[Sucesión de Fibonacci|números de Fibonacci]] mediante técnicas de funcións xeradoras.

=== Operacións sobre funcións xeradoras ===

==== A multiplicación produce convolución ====
A multiplicación de funcións xeradoras ordinarias produce unha [[convolución]] discreta ([[produto de Cauchy]]) das secuencias. Por exemplo, a secuencia de sumas acumuladas (compare coa fórmula de Euler-Maclaurin que é un pouco máis xeral) <math display="block">(a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots)</math>dunha secuencia con función xeradora ordinaria {{Math|''G''(''a<sub>n</sub>''; ''x'')}} ten a función xeradora <math display="block">G(a_n; x) \cdot \frac{1}{1-x}</math> porque <math> \frac{1}{1-x} </math> é a función xeradora ordinaria para a secuencia {{nowrap|(1, 1, ...)}}.

==== Índices de secuencia desprazados ====
Para os enteiros {{Math|''m'' ≥ 1}}, temos as seguintes dúas identidades análogas para as funcións xeradoras modificadas que enumeran as variantes de secuencia desprazada de {{Math|⟨ ''g''<sub>''n'' − ''m''</sub> ⟩}} e {{Math|⟨ ''g''<sub>''n'' + ''m''</sub> ⟩}}, respectivamente: <math display="block">\begin{align}
& z^m G(z) = \sum_{n = m}^\infty g_{n-m} z^n \\[4px]
& \frac{G(z) - g_0 - g_1 z - \cdots - g_{m-1} z^{m-1}}{z^m} = \sum_{n = 0}^\infty g_{n+m} z^n.
\end{align}</math>

==== Diferenciación e integración de funcións xeradoras ====
Temos respectivamente as seguintes expansións de series de potencias para a primeira derivada dunha función xeradora e a súa integral: <math display="block">\begin{align}
G'(z) & = \sum_{n = 0}^\infty (n+1) g_{n+1} z^n. \\[4px]
z \cdot G'(z) & = \sum_{n = 0}^\infty n g_{n} z^n. \\[4px]
\int_0^z G(t) \, dt & = \sum_{n = 1}^\infty \frac{g_{n-1}}{n} z^n.
\end{align}</math>

A operación de diferenciación-multiplicación da segunda identidade pódese repetir {{Mvar|k}} veces para multiplicar a secuencia por {{Math|''n''<sup>''k''</sup>}}, mais iso require alternar a diferenciación e a multiplicación. Se en torques se fai {{Mvar|k}} diferenciacións en secuencia, o efecto é multiplicar polo {{Mvar|k}}-ésimo [[Factorial descendente e ascendente|factorial descendente]]: <math display="block"> z^k G^{(k)}(z) = \sum_{n = 0}^\infty n^\underline{k} g_n z^n = \sum_{n = 0}^\infty n (n-1) \dotsb (n-k+1) g_n z^n \quad\text{for all } k \in \mathbb{N}. </math>

== Exemplos ==

=== Números cadrados ===
As funcións xeradoras para a secuencia de [[Cadrado perfecto|números cadrados]] {{Math|''a''<sub>''n''</sub> {{=}} ''n''<sup>2</sup>}} son:
{| class="wikitable"
!Tipo de función xeradora
! Ecuación
|-
| Función xeradora ordinaria
| <math>G(n^2;x)=\sum_{n=0}^\infty n^2x^n = \frac{x(x+1)}{(1-x)^3}</math>
|-
| Función xeradora exponencial
| <math>\operatorname{EG}(n^2;x)=\sum _{n=0}^\infty \frac{n^2x^n}{n!}=x(x+1)e^x</math>
|-
| Serie de Bell
| <math>\operatorname{BG}_p\left(n^2;x\right)=\sum_{n=0}^\infty \left(p^{n}\right)^2x^n=\frac{1}{1-p^2x}</math>
|-
| Serie de Dirichlet
| <math>\operatorname{DG}\left(n^2;s\right)=\sum_{n=1}^\infty \frac{n^2}{n^s}=\zeta(s-2)</math>
|}
onde {{Math|''ζ''(''s)''}} é a [[función zeta de Riemann]].

== Notas ==
{{reflist|30em}} 

== Véxase tamén ==

=== Bibliografía ===
*{{cita libro  |first=Martin |last=Aigner |title=A Course in Enumeration |url=https://books.google.com/books?id=pPEJcu93dzAC |date=2007 |publisher=Springer |isbn=978-3-540-39035-0 |series=Graduate Texts in Mathematics |volume=238 }}
* {{cita publicación periódica |title=On the foundations of combinatorial theory. VI. The idea of generating function |last1=Doubilet |first1=Peter |last2=Rota | first2=Gian-Carlo | author2-link=Gian-Carlo Rota | last3=Stanley | first3=Richard | author3-link=Richard P. Stanley | journal=Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability |volume=2 |pages=267–318 |year=1972 | zbl=0267.05002 | url=http://projecteuclid.org/euclid.bsmsp/1200514223 }} Reprinted in {{cita libro  | last=Rota | first=Gian-Carlo | author-link=Gian-Carlo Rota | others=With the collaboration of P. Doubilet, C. Greene, D. Kahaner, [[Andrew Odlyzko|A. Odlyzko]] and [[Richard P. Stanley|R. Stanley]] | title=Finite Operator Calculus | url=https://archive.org/details/finiteoperatorca0000rota | chapter=3. The idea of generating function | pages=[https://archive.org/details/finiteoperatorca0000rota/page/n98 83]–134 | publisher=Academic Press | year=1975 | isbn=0-12-596650-4 | zbl=0328.05007 }}
* {{cita libro | last1 = Flajolet | first1 = Philippe | author-link1 = Philippe Flajolet | last2 = Sedgewick | first2 = Robert | author-link2 = Robert Sedgewick (computer scientist) | title = Analytic Combinatorics | title-link= Analytic Combinatorics | year = 2009 | publisher = Cambridge University Press | isbn = 978-0-521-89806-5 | zbl=1165.05001 }}
* {{cita libro | last1 = Goulden | first1 = Ian P. | last2 = Jackson | first2 = David M. | author-link2 = David M. Jackson | title = Combinatorial Enumeration | year = 2004 | publisher = [[Dover Publications]] | isbn = 978-0486435978 }}
* {{cita libro |title=[[Concrete Mathematics|Concrete Mathematics. A foundation for computer science]] |edition=2nd |year=1994 |publisher=Addison-Wesley |isbn=0-201-55802-5 |chapter=Chapter 7: Generating Functions |pages=320–380| zbl=0836.00001 |first1 = Ronald L. |last1=Graham |first2 = Donald E. |last2=Knuth |first3=Oren |last3=Patashnik |author-link1=Ronald Graham |author-link2=Donald Knuth |author-link3=Oren Patashnik }}
*{{cita libro |first=Sergei K. |last=Lando |title=Lectures on Generating Functions |url=https://books.google.com/books?id=A6_4AwAAQBAJ |date=2003 |publisher=American Mathematical Society |isbn=978-0-8218-3481-7 }}
* {{cita libro | last=Wilf | first=Herbert S. | author-link=Herbert Wilf | title=Generatingfunctionology | edition=2nd | publisher=Academic Press | year=1994 | isbn=0-12-751956-4 | zbl=0831.05001 | url=http://www.math.upenn.edu/%7Ewilf/DownldGF.html }}
=== Outros artigos ===
* [[Transformacións de funcións xeradoras]]
* [[Teorema da reprocidade de Stanley]]
* [[Partición dun enteiro]]
* [[Principios de combinatoria]]
=== Ligazóns externas ===
* [http://garsia.math.yorku.ca/~zabrocki/MMM1/MMM1Intro2OGFs.pdf "Introduction To Ordinary Generating Functions"] by Mike Zabrocki, York University, Mathematics and Statistics
* {{springer|title=Generating function|id=p/g043900}}
* [http://www.cut-the-knot.org/ctk/GeneratingFunctions.shtml Generating Functions, Power Indices and Coin Change] at [[cut-the-knot]]
* [http://demonstrations.wolfram.com/GeneratingFunctions/ "Generating Functions"] by [[Ed Pegg Jr.]], [[Wolfram Demonstrations Project]], 2007.


{{control de autoridades}}
[[Categoría:Teoría de números]]
[[Categoría:Combinatoria]]
[[Categoría:Wikipedia:Páxinas con traducións non revisadas]]
[[Categoría:Serie matemática]]
[[Categoría:Funcións]]