Función xeradora

En matemáticas, unha función xeradora é unha representación dunha secuencia infinita de números como os 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 $f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots$ onde $a_{0},a_{1},a_{2},\cdots$ son os termos da secuencia a considerar. Resulta útil e frecuente representar a función xeradora mediante unha forma pechada.

Exemplo: Para a secuencia: $1,3,9,27,\cdots$ temos a función xeradora ordinaria $f(x)=1+3x+9x^{2}+27x^{3}+\cdots$. Podemos obter unha forma pechada usando a serie xeométrica, $f(x)={\dfrac {1}{1-3x}}$. Se atendemos a esa igualdade como unha función normal só se cumpriría para valores de x menores a $3/4$ 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 $a_{n}$ dunha serie formal de potencias $f(x)$ úsase a potencia de x fechada entre corchetes. Así $[x^{n}]f(x)$ quere dicir "o coeficiente de $x^{n}$ na función $f(x)$.

Por exemplo:

$[x^{n}]e^{x}=1/n!;\quad [u^{m}](1+u)^{s}={\binom {s}{m}}$.

Converxencia

A diferenza dunha serie ordinaria, a serie formal de potencias non está obrigada a 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 a un codominio.

Limitacións

Non todas as expresións que teñen significado como funcións de x son significativas como expresións que designan series formais; por exemplo, as potencias negativas ou de fracción de 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 a_n é:

$G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.$

Se a_n é a función de masa de probabilidade dunha variábel aleatoria discreta, entón a súa función xeradora ordinaria chámase función xeradora de probabilidade.

Función xeradora exponencial (EGF)

A función xeradora exponencial dunha secuencia a_n é

$\operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.$

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.

Función xeradora de Poisson

A función xeradora de Poisson dunha secuencia a_n é

$\operatorname {PG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}e^{-x}{\frac {x^{n}}{n!}}=e^{-x}\,\operatorname {EG} (a_{n};x).$

Serie de Lambert

A serie de Lambert dunha sucesión a_n é

$\operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.$

Teña en conta que nunha serie de Lambert o índice 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

$b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x)$

para os enteiros n ≥ 1 están relacionados pola suma dos divisores

$b_{n}=\sum _{d|n}a_{d}.$

Onde $[x^{n}]$ é o coeficiente da potencia $x^{n}$ como vimos na notación.

Serie de Bell

A serie de Bell dunha sucesión a_n é unha expresión en termos tanto dunha x indeterminada como dun p primo e vén dada por:

$\operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.$

Funcións xeradoras de series de Dirichlet (DGF)

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 a_n é:

$\operatorname {DG} (a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.$

A función xeradora en serie de Dirichlet é especialmente útil cando a_n é unha función multiplicativa, nese caso ten unha expresión como produto de Euler en termos da serie de Bell da función:

$\operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,.$

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:

$e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}$

onde p_n(x) é unha secuencia de polinomios e f(t) é unha función dunha determinada forma. 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 secuencias polinómicas xeradas por funcións xeradoras máis complexas inclúen:

• Polinomios de Appell
• Polinomios de Chebyshev
• Polinomios por diferencias
• Polinomios de Appell xeneralizados
• Polinomios por q-diferencias

Funcións xeradoras ordinarias

Exemplos de secuencias sinxelas

Unha función xeradora fundamental é a da secuencia constante 1, 1, 1, 1, 1, 1, 1, 1, 1, ... , cuxa función xeradora ordinaria é a serie xeométrica

$\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}.$

O lado esquerdo é a expansión da 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 x → ax dá a función xeradora para a secuencia xeométrica 1, a, a², a³, ... para calquera constante a

$\sum _{n=0}^{\infty }(ax)^{n}={\frac {1}{1-ax}}.$

(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,

$\sum _{n=0}^{\infty }(-1)^{n}x^{n}={\frac {1}{1+x}}.$

Tamén se poden introducir ocos regulares na secuencia substituíndo x por algunha potencia de x, así, por exemplo, para a secuencia 1, 0, 1, 0, 1, 0, 1, 0, ... (que salta sobre x, x³, x⁵, ... ) obtense a función xeradora

$\sum _{n=0}^{\infty }x^{2n}={\frac {1}{1-x^{2}}}.$

Ao elevar ao cadrado a función xeradora inicial, ou achar a derivada de ambos os dous lados con respecto a x e facer un cambio da variábel n → n + 1, vese que os coeficientes forman a secuencia 1, 2, 3, 4, 5, ... , así un ten

$\sum _{n=0}^{\infty }(n+1)x^{n}={\frac {1}{(1-x)^{2}}},$

e a terceira potencia ten como coeficientes os números triangulares 1, 3, 6, 10, 15, 21, ... cuxo termo n é o coeficiente binomial ${\binom {n+2}{2}}$, de xeito que

$\sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{n}={\frac {1}{(1-x)^{3}}}.$

Por indución, podemos mostrar de xeito similar para os enteiros positivos m ≥ 1 que

$n^{m}=\sum _{j=0}^{m}{\begin{Bmatrix}m\\j\end{Bmatrix}}{\frac {n!}{(n-j)!}},$

onde {n
k} denota os números de Stirling do segundo tipo e onde temos a función xeradora

$\sum _{n=0}^{\infty }{\frac {n!}{(n-j)!}}\,z^{n}={\frac {j!\cdot z^{j}}{(1-z)^{j+1}}},$

de xeito que podemos formar as funcións xeradoras análogas sobre as potencias enteiras m-ésimas xeneralizando o resultado no caso do cadrado anterior. En particular, xa que podemos escribir

${\frac {z^{k}}{(1-z)^{k+1}}}=\sum _{i=0}^{k}{\binom {k}{i}}{\frac {(-1)^{k-i}}{(1-z)^{i+1}}},$

podemos aplicar unha coñecida identidade de suma finita que inclúe os números de Stirling para obter que

$\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}}}.$

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 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 linear de diferenzas finitas con coeficientes constantes. O exemplo prototípico aquí é derivar a fórmula de Binet para os 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) $$(a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )$$dunha secuencia con función xeradora ordinaria G(a_n; x) ten a función xeradora $$G(a_{n};x)\cdot {\frac {1}{1-x}}$$ porque ${\frac {1}{1-x}}$ é a función xeradora ordinaria para a secuencia (1, 1, ...).

Índices de secuencia desprazados

Para os enteiros m ≥ 1, temos as seguintes dúas identidades análogas para as funcións xeradoras modificadas que enumeran as variantes de secuencia desprazada de ⟨ g_{n − m} ⟩ e ⟨ g_{n + m} ⟩, respectivamente: $${\begin{aligned}&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{aligned}}$$

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: $${\begin{aligned}G'(z)&=\sum _{n=0}^{\infty }(n+1)g_{n+1}z^{n}.\\[4px]z\cdot G'(z)&=\sum _{n=0}^{\infty }ng_{n}z^{n}.\\[4px]\int _{0}^{z}G(t)\,dt&=\sum _{n=1}^{\infty }{\frac {g_{n-1}}{n}}z^{n}.\end{aligned}}$$

A operación de diferenciación-multiplicación da segunda identidade pódese repetir k veces para multiplicar a secuencia por n^k, mais iso require alternar a diferenciación e a multiplicación. Se en torques se fai k diferenciacións en secuencia, o efecto é multiplicar polo k-ésimo factorial descendente: $$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} .$$

Exemplos

Números cadrados

As funcións xeradoras para a secuencia de números cadrados a_n = n² son:

Tipo de función xeradora	Ecuación
Función xeradora ordinaria	$G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}$
Función xeradora exponencial	$\operatorname {EG} (n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}$
Serie de Bell	$\operatorname {BG} _{p}\left(n^{2};x\right)=\sum _{n=0}^{\infty }\left(p^{n}\right)^{2}x^{n}={\frac {1}{1-p^{2}x}}$
Serie de Dirichlet	$\operatorname {DG} \left(n^{2};s\right)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2)$

onde ζ(s) é a función zeta de Riemann.

Véxase tamén

Bibliografía

• Aigner, Martin (2007). A Course in Enumeration. Graduate Texts in Mathematics 238. Springer. ISBN 978-3-540-39035-0. 
• Doubilet, Peter; Rota, Gian-Carlo; Stanley, Richard (1972). "On the foundations of combinatorial theory. VI. The idea of generating function". Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability 2: 267–318. Zbl 0267.05002.  Reprinted in Rota, Gian-Carlo (1975). "3. The idea of generating function". Finite Operator Calculus. With the collaboration of P. Doubilet, C. Greene, D. Kahaner, A. Odlyzko and R. Stanley. Academic Press. pp. 83–134. ISBN 0-12-596650-4. Zbl 0328.05007. 
• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics. Cambridge University Press. ISBN 978-0-521-89806-5. Zbl 1165.05001. 
• Goulden, Ian P.; Jackson, David M. (2004). Combinatorial Enumeration. Dover Publications. ISBN 978-0486435978. 
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). "Chapter 7: Generating Functions". Concrete Mathematics. A foundation for computer science (2nd ed.). Addison-Wesley. pp. 320–380. ISBN 0-201-55802-5. Zbl 0836.00001. 
• Lando, Sergei K. (2003). Lectures on Generating Functions. American Mathematical Society. ISBN 978-0-8218-3481-7. 
• Wilf, Herbert S. (1994). Generatingfunctionology (2nd ed.). Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001. 

Outros artigos

• Transformacións de funcións xeradoras
• Teorema da reprocidade de Stanley
• Partición dun enteiro
• Principios de combinatoria

Ligazóns externas

• "Introduction To Ordinary Generating Functions" by Mike Zabrocki, York University, Mathematics and Statistics
• "Generating function". Encyclopedia of Mathematics. EMS Press. 2001 [1994]. 
• Generating Functions, Power Indices and Coin Change at cut-the-knot
• "Generating Functions" by Ed Pegg Jr., Wolfram Demonstrations Project, 2007.