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  onde  son os termos da secuencia a considerar. Resulta útil e frecuente representar a función xeradora mediante unha forma pechada.

Exemplo:  Para a secuencia:  temos a función xeradora ordinaria . Podemos obter unha forma pechada usando a serie xeométrica, .
Se atendemos a esa igualdade como unha función normal só se cumpriría para valores de  menores a  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  dunha serie formal de potencias   úsase a potencia de  fechada entre corchetes. Así  quere dicir "o coeficiente de  na función .

Por exemplo:
.

 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  son significativas como expresións que designan series formais; por exemplo, as potencias negativas ou de fracción de  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  é: 

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  é 


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  é 

 Serie de Lambert 
A serie de Lambert dunha sucesió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 

para os enteiros  están relacionados pola suma dos divisores 

Onde  é o coeficiente da potencia  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: 


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


 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: 

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 

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 


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


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 


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 


e a terceira potencia ten como coeficientes os números triangulares  cuxo termo  é o coeficiente binomial , de xeito que 


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


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


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 


podemos aplicar unha coñecida identidade de suma finita que inclúe os números de Stirling para obter que  for finite sum identities involving the Stirling number triangles. 

 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) dunha secuencia con función xeradora ordinaria  ten a función xeradora  porque  é 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: 

 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: 

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: 

 Exemplos 

 Números cadrados 
As funcións xeradoras para a secuencia de números cadrados  son:
Tipo de función xeradora Ecuación Función xeradora ordinaria  Función xeradora exponencial  Serie de Bell  Serie de Dirichlet 
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.

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