Función xeradora

serie formal de potencias con coeficientes que codifican información sobre unha secuencia

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

editar

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 x 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 x fechada entre corchetes. Así   quere dicir "o coeficiente de   na función  .[1]

Por exemplo:

 .

Converxencia

editar

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

editar

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.

Función xeradora ordinaria (OGF)

editar

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

 

Se an é 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)

editar

A función xeradora exponencial dunha secuencia an é

 

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.[2]

Función xeradora de Poisson

editar

A función xeradora de Poisson dunha secuencia an é

 

Serie de Lambert

editar

A serie de Lambert dunha sucesión an é

 

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

 

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

 

Onde   é o coeficiente da potencia   como vimos na notación.

Serie de Bell

editar

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

 

Funcións xeradoras de series de Dirichlet (DGF)

editar

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 an é: [3]

 

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

 

Funcións xeradoras de secuencias polinómicas

editar

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

Funcións xeradoras ordinarias

editar

Exemplos de secuencias sinxelas

editar

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

 

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 xax dá a función xeradora para a secuencia xeométrica 1, a, a2, a3, ... para calquera constante a

 

(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 x por algunha potencia de x, así, por exemplo, para a secuencia 1, 0, 1, 0, 1, 0, 1, 0, ... (que salta sobre x, x3, x5, ... ) 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 x e facer un cambio da variábel nn + 1, vese que os coeficientes forman a secuencia 1, 2, 3, 4, 5, ... , así un ten

 

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

 

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

 

onde {n
k
}
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 m-é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 [7]

 

Funcións racionais

editar

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

editar

A multiplicación produce convolución

editar

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 G(an; x) ten a función xeradora   porque   é a función xeradora ordinaria para a secuencia (1, 1, ...).

Índices de secuencia desprazados

editar

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 gnm e gn + m, respectivamente:  

Diferenciación e integración de funcións xeradoras

editar

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 k veces para multiplicar a secuencia por nk, 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:  

Exemplos

editar

Números cadrados

editar

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

Tipo de función xeradora Ecuación
Función xeradora ordinaria  
Función xeradora exponencial  
Serie de Bell  
Serie de Dirichlet  

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

  1. Wilf, Herbert S. (1990). generatingfunctionology. Academic Press, Inc. 
  2. Flajolet & Sedgewick 2009, p. 95
  3. Wilf 1994, p. 56
  4. Wilf 1994, p. 59
  5. Spivey, Michael Z. (2007). "Combinatorial Sums and Finite Differences". Discrete Math. 307 (24): 3130–3146. MR 2370116. doi:10.1016/j.disc.2007.03.052. 
  6. Mathar, R. J. (2012). "Yet another table of integrals". arXiv:1207.5845 [math.CA]. 
  7. Graham, Knuth & Patashnik 1994 for finite sum identities involving the Stirling number triangles.

Véxase tamén

editar

Bibliografía

editar

Outros artigos

editar

Ligazóns externas

editar