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 + 3 x + 9 x^2 + 27 x^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  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  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&nbsp; son significativas como expresións que designan series formais; por exemplo, as potencias negativas ou de fracción de&nbsp; 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  é: 
: G(a_n;x)=\sum_{n=0}^\infty a_n x^n.
Se  é 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  é 
: \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  é 
:\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  é 
:\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  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  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  é unha expresión en termos tanto dunha  indeterminada como dun  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  é:  
: \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  é 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  é unha secuencia de polinomios e  é 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 diferenzas
* Polinomios de Appell xeneralizados
* Polinomios por -diferenzas

## Funcións xeradoras ordinarias 
### Exemplos de secuencias sinxelas 
Unha función xeradora fundamental é a da secuencia constante  , 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  dá a función xeradora para a secuencia xeométrica  para calquera constante 
: \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)^nx^n= \frac{1}{1+x}.

Tamén se poden introducir ocos regulares na secuencia substituíndo  por algunha potencia de , así, por exemplo, para a secuencia  (que salta sobre  ) 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  e facer un cambio da variábel  , vese que os coeficientes forman a secuencia  , 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  cuxo termo  é 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  que
: n^m = \sum_{j=0}^m \begin{Bmatrix} m \\ j \end{Bmatrix} \frac{n!}{(n-j)!}, 

onde {{Math|{{resize|150%|{}}{{resize|150%|}}}}} 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 -é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  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 .

#### Índices de secuencia desprazados 
Para os enteiros , temos as seguintes dúas identidades análogas para as funcións xeradoras modificadas que enumeran as variantes de secuencia desprazada de  e , respectivamente: \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}

#### 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{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}

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

onde  é a función zeta de Riemann.

## Notas 
## Véxase tamén 
### Bibliografía 
*
*  Reprinted in 
* 
* 
* 
*
* 
### 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 Functions, Power Indices and Coin Change at cut-the-knot
* "Generating Functions" by Ed Pegg Jr., Wolfram Demonstrations Project, 2007.