función generadora

Serie de potencias formales; Los coeficientes codifican información sobre una secuencia indexada por números naturales.

En matemáticas , una función generadora es una representación de una secuencia infinita de números como los coeficientes de una serie de potencias formal . A diferencia de una serie ordinaria, no es necesario que la serie de potencias formal converja : de hecho, la función generadora no se considera realmente como una función , y la "variable" sigue siendo un indeterminado . Las funciones generadoras fueron introducidas por primera vez por Abraham de Moivre en 1730, para resolver el problema general de recurrencia lineal. ^[1] Se puede generalizar a series de potencias formales en más de un indeterminado, para codificar información sobre infinitas matrices multidimensionales de números.

Existen varios tipos de funciones generadoras, incluidas funciones generadoras ordinarias , funciones generadoras exponenciales , series de Lambert , series de Bell y series de Dirichlet ; A continuación se dan definiciones y ejemplos. En principio, cada secuencia tiene una función generadora de cada tipo (excepto que las series de Lambert y Dirichlet requieren que los índices comiencen en 1 en lugar de 0), pero la facilidad con la que se pueden manejar puede diferir considerablemente. La función generadora particular, si la hay, que sea más útil en un contexto dado dependerá de la naturaleza de la secuencia y de los detalles del problema que se aborda.

Las funciones generadoras a menudo se expresan en forma cerrada (en lugar de como una serie), mediante alguna expresión que implique operaciones definidas para series formales. Estas expresiones en términos del indeterminado  x pueden implicar operaciones aritméticas, diferenciación con respecto a  x y composición con (es decir, sustitución en) otras funciones generadoras; Dado que estas operaciones también están definidas para funciones, el resultado parece una función de  x . De hecho, la expresión de forma cerrada a menudo puede interpretarse como una función que puede evaluarse en valores concretos (suficientemente pequeños) de x , y que tiene la serie formal como su expansión de serie ; esto explica la denominación "funciones generadoras". Sin embargo, no es necesario que tal interpretación sea posible, porque no se requiere que las series formales den una serie convergente cuando se sustituye x por un valor numérico distinto de cero  . Además, no todas las expresiones que son significativas como funciones de  x lo son como expresiones que designan series formales; por ejemplo, las potencias negativas y fraccionarias de  x son ejemplos de funciones que no tienen una serie de potencias formal correspondiente.

Las funciones generadoras no son funciones en el sentido formal de un mapeo de un dominio a un codominio . Las funciones generadoras a veces se denominan series generadoras , ^[2] en el sentido de que se puede decir que una serie de términos es el generador de su secuencia de coeficientes de términos.

Definiciones

Una función generadora es un dispositivo algo similar a una bolsa. En lugar de llevar muchos objetos pequeños por separado, lo que podría resultar embarazoso, los metemos todos en una bolsa y luego solo nos queda un objeto para llevar: la bolsa.

—  George Pólya , Matemáticas y razonamiento plausible (1954)

Una función generadora es un tendedero en el que colgamos una secuencia de números para mostrarlos.

—  Herbert Wilf , Funcionalidad generadora (1994)

Función generadora ordinaria (OGF)

La función generadora ordinaria de una secuencia an _es

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

Cuando el término función generadora se utiliza sin reservas, normalmente se entiende que se refiere a una función generadora ordinaria.

Si an es la función de masa de probabilidad de una variable aleatoria discreta _, entonces su función generadora ordinaria se llama función generadora de probabilidad .

La función generadora ordinaria se puede generalizar a matrices con múltiples índices. Por ejemplo, la función generadora ordinaria de una matriz bidimensional a _{m , n} (donde n y m son números naturales) es

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

Función generadora exponencial (EGF)

La función generadora exponencial de una secuencia an _es

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

Las funciones generadoras exponenciales son generalmente más convenientes que las funciones generadoras ordinarias para problemas de enumeración combinatoria que involucran objetos etiquetados. ^[3]

Otro beneficio de las funciones generadoras exponenciales es que son útiles para transferir relaciones de recurrencia lineal al ámbito de las ecuaciones diferenciales . Por ejemplo, tomemos la secuencia de Fibonacci { f _n } que satisface la relación de recurrencia lineal f _{n +2} = f _{n +1} + f _n . La función generadora exponencial correspondiente tiene la forma

$${\displaystyle \operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}}$$

y se puede demostrar fácilmente que sus derivadas satisfacen la ecuación diferencial EF″( x ) = EF ′ ( x ) + EF( x ) como analogía directa de la relación de recurrencia anterior. Desde este punto de vista, el término factorial n ! es simplemente un contratérmino para normalizar el operador derivativo que actúa sobre x ⁿ .

Función generadora de veneno

La función generadora de Poisson _de una secuencia an es

$${\displaystyle \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 lamberto

La serie de Lambert de una secuencia a _n es

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

Los coeficientes de la serie de Lambert en las expansiones de series de potencias.

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

para números enteros n ≥ 1 están relacionados por la suma del divisor

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

El artículo principal proporciona varios ejemplos más clásicos, o al menos conocidos, relacionados con funciones aritméticas especiales en la teoría de números .

En una serie de Lambert, el índice n comienza en 1, no en 0, ya que de otro modo el primer término no estaría definido.

serie campana

La serie _de Bell de una secuencia an es una expresión en términos de una x indeterminada y de un p primo y está dada por ^[4]

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

Funciones generadoras de series de Dirichlet (DGF)

Las series formales de Dirichlet a menudo se clasifican como funciones generadoras, aunque no son series de potencias estrictamente formales. La función generadora de series de Dirichlet _de una secuencia an es ^[5]

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

La función generadora de series de Dirichlet es especialmente útil cuando una _n es una función multiplicativa , en cuyo caso tiene una expresión del producto de Euler ^[6] en términos de la serie de Bell de la función.

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

Si una _n es un carácter de Dirichlet , entonces su función generadora de series de Dirichlet se denomina serie L de Dirichlet . También tenemos una relación entre el par de coeficientes en las expansiones de la serie de Lambert anteriores y sus FGD. Es decir, podemos probar que

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

si y solo si

$${\displaystyle \operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s),}$$

donde ζ ( s ) es la función zeta de Riemann . ^[7]

Funciones generadoras de secuencias polinomiales

La idea de generar funciones se puede extender a secuencias de otros objetos. Así, por ejemplo, las secuencias polinómicas de tipo binomial se generan mediante

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

donde p _n ( x ) es una secuencia de polinomios y f ( t ) es una función de cierta forma. Las secuencias de Sheffer se generan de manera similar. Consulte el artículo principal Polinomios de Appell generalizados para obtener más información.

Funciones generadoras ordinarias

Ejemplos de generación de funciones para secuencias simples.

Los polinomios son un caso especial de funciones generadoras ordinarias, correspondientes a secuencias finitas o, de manera equivalente, secuencias que desaparecen después de cierto punto. Estos son importantes porque muchas secuencias finitas pueden interpretarse de manera útil como funciones generadoras, como el polinomio de Poincaré y otros.

Una función generadora fundamental es la de la secuencia constante 1, 1, 1, 1, 1, 1, 1, 1, 1, ... , cuya función generadora ordinaria es la serie geométrica

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

El lado izquierdo es la expansión en serie de Maclaurin del lado derecho. Alternativamente, la igualdad se puede justificar multiplicando la serie de potencias de la izquierda por 1 − x , y comprobando que el resultado es la serie de potencias constante 1 (en otras palabras, que todos los coeficientes excepto el de x ⁰ son iguales a 0) . Además, no puede haber otra serie de potencias con esta propiedad. Por tanto, el lado izquierdo designa el inverso multiplicativo de 1 − x en el anillo de series de potencias.

Las expresiones para la función generadora ordinaria de otras secuencias se derivan fácilmente de ésta. Por ejemplo, la sustitución x → ax da la función generadora de la secuencia geométrica 1, a , a ² , a ³ , ... para cualquier constante a :

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

(La igualdad también se deriva directamente del hecho de que el lado izquierdo es el desarrollo en serie de Maclaurin del lado derecho.) En particular,

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

También se pueden introducir espacios regulares en la secuencia reemplazando x por alguna potencia de x , así por ejemplo para la secuencia 1, 0, 1, 0, 1, 0, 1, 0, ... (que omite x , x ³ , x ⁵ , ... ) se obtiene la función generadora

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

Al elevar al cuadrado la función generadora inicial, o al encontrar la derivada de ambos lados con respecto a x y hacer un cambio de la variable de ejecución n → n + 1 , se ve que los coeficientes forman la secuencia 1, 2, 3, 4, 5, ... , entonces uno tiene

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

y la tercera potencia tiene como coeficientes los números triangulares 1, 3, 6, 10, 15, 21,... cuyo término n es el coeficiente binomial (^{norte + 2}
₂) , de modo que

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

De manera más general, para cualquier entero no negativo k y valor real distinto de cero a , es cierto que

$${\displaystyle \sum _{n=0}^{\infty }a^{n}{\binom {n+k}{k}}x^{n}={\frac {1}{(1-ax)^{k+1}}}\,.}$$

Desde

$${\displaystyle 2{\binom {n+2}{2}}-3{\binom {n+1}{1}}+{\binom {n}{0}}=2{\frac {(n+1)(n+2)}{2}}-3(n+1)+1=n^{2},}$$

se puede encontrar la función generadora ordinaria para la secuencia 0, 1, 4, 9, 16, ... de números cuadrados mediante una combinación lineal de secuencias generadoras de coeficientes binomiales:

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

También podemos expandir alternativamente para generar esta misma secuencia de cuadrados como suma de derivadas de la serie geométrica de la siguiente forma:

$${\displaystyle {\begin{aligned}G(n^{2};x)&=\sum _{n=0}^{\infty }n^{2}x^{n}\\[4px]&=\sum _{n=0}^{\infty }n(n-1)x^{n}+\sum _{n=0}^{\infty }nx^{n}\\[4px]&=x^{2}D^{2}\left[{\frac {1}{1-x}}\right]+xD\left[{\frac {1}{1-x}}\right]\\[4px]&={\frac {2x^{2}}{(1-x)^{3}}}+{\frac {x}{(1-x)^{2}}}={\frac {x(x+1)}{(1-x)^{3}}}.\end{aligned}}}$$

Por inducción, podemos demostrar de manera similar para números enteros positivos m ≥ 1 que ^{[8] [9]}

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

dónde {^nk
_{_}} denota los números de Stirling de segundo tipo y donde la función generadora

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

de modo que podamos formar funciones generadoras análogas sobre la integral m- ésima potencias generalizando el resultado en el caso cuadrado anterior. En particular, dado que podemos escribir

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

podemos aplicar una identidad de suma finita bien conocida que involucra los números de Stirling para obtener eso ^[10]

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

Funciones racionales

La función generadora ordinaria de una secuencia se puede expresar como una función racional (la relación de dos polinomios de grado finito) si y sólo si la secuencia es una secuencia recursiva lineal con coeficientes constantes; esto generaliza los ejemplos anteriores. Por el contrario, toda secuencia generada por una fracción de polinomios satisface una recurrencia lineal con coeficientes constantes; estos coeficientes son idénticos a los coeficientes del polinomio del denominador de fracción (por lo que se pueden leer directamente). Esta observación muestra que es fácil de resolver para generar funciones de secuencias definidas por una ecuación lineal en diferencias finitas con coeficientes constantes y, por lo tanto, para fórmulas explícitas de forma cerrada para los coeficientes de estas funciones generadoras. El ejemplo prototípico aquí es derivar la fórmula de Binet para los números de Fibonacci mediante técnicas de generación de funciones.

También notamos que la clase de funciones generadoras racionales corresponde precisamente a las funciones generadoras que enumeran secuencias cuasipolinomiales de la forma ^[11]

$${\displaystyle f_{n}=p_{1}(n)\rho _{1}^{n}+\cdots +p_{\ell }(n)\rho _{\ell }^{n},}$$

donde las raíces recíprocas, son escalares fijos y donde p _i ( n ) es un polinomio en n para todo 1 ≤ i ≤ ℓ . ${\displaystyle \rho _{i}\in \mathbb {C} }$

En general, los productos Hadamard de funciones racionales producen funciones generadoras racionales. De manera similar, si

$${\displaystyle F(s,t):=\sum _{m,n\geq 0}f(m,n)w^{m}z^{n}}$$

es una función generadora racional bivariada, entonces su correspondiente función generadora diagonal ,

$${\displaystyle \operatorname {diag} (F):=\sum _{n=0}^{\infty }f(n,n)z^{n},}$$

es algebraico . Por ejemplo, si dejamos ^[12]

$${\displaystyle F(s,t):=\sum _{i,j\geq 0}{\binom {i+j}{i}}s^{i}t^{j}={\frac {1}{1-s-t}},}$$

entonces la función generadora del coeficiente diagonal de esta función generadora viene dada por la conocida fórmula OGF

$${\displaystyle \operatorname {diag} (F)=\sum _{n=0}^{\infty }{\binom {2n}{n}}z^{n}={\frac {1}{\sqrt {1-4z}}}.}$$

Este resultado se calcula de muchas maneras, incluida la fórmula integral de Cauchy o la integración de contorno , tomando residuos complejos o mediante manipulaciones directas de series de potencias formales en dos variables.

Operaciones sobre funciones generadoras.

La multiplicación produce convolución

La multiplicación de funciones generadoras ordinarias produce una convolución discreta (el producto de Cauchy ) de las secuencias. Por ejemplo, la secuencia de sumas acumulativas (compárese con la fórmula ligeramente más general de Euler-Maclaurin )

$${\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )}$$

G ( a _n ; x )

$${\displaystyle G(a_{n};x)\cdot {\frac {1}{1-x}}}$$

1/1- x(1, 1, ...)

Índices de secuencia cambiante

Para números enteros m ≥ 1 , tenemos las siguientes dos identidades análogas para las funciones generadoras modificadas que enumeran las variantes de secuencia desplazadas de ⟨ g _{n − m} ⟩ y ⟨ g _{n + m} ⟩ , respectivamente:

$${\displaystyle {\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 funciones generadoras.

Tenemos las siguientes expansiones de series de potencias respectivas para la primera derivada de una función generadora y su integral:

$${\displaystyle {\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}}}$$

La operación de diferenciación-multiplicación de la segunda identidad se puede repetir k veces para multiplicar la secuencia por n ^k , pero eso requiere alternar entre diferenciación y multiplicación. Si en lugar de hacer k diferenciaciones en secuencia, el efecto es multiplicar por el k ésimo factorial que cae :

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

Usando los números de Stirling del segundo tipo , se pueden convertir en otra fórmula para multiplicar por de la siguiente manera (consulte el artículo principal sobre cómo generar transformaciones de funciones ): ${\displaystyle n^{k}}$

$${\displaystyle \sum _{j=0}^{k}{\begin{Bmatrix}k\\j\end{Bmatrix}}z^{j}F^{(j)}(z)=\sum _{n=0}^{\infty }n^{k}f_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .}$$

Una inversión de orden negativo de esta fórmula de potencias de secuencia correspondiente a la operación de integración repetida se define mediante la transformación en serie zeta y sus generalizaciones definidas como una transformación basada en derivadas de funciones generadoras , o alternativamente en términos de y realizando una transformación integral en la secuencia. función generadora. Aquí se analizan las operaciones relacionadas para realizar la integración fraccionaria en una función generadora de secuencia .

Enumerar progresiones aritméticas de secuencias

En esta sección damos fórmulas para generar funciones que enumeran la secuencia { f _{an + b} } dada una función generadora ordinaria F ( z ) , donde a ≥ 2 , 0 ≤ b < a , y a y b son números enteros (consulte el artículo principal sobre transformaciones ). Para a = 2 , esto es simplemente la conocida descomposición de una función en partes pares e impares (es decir, potencias pares e impares):

$${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }f_{2n}z^{2n}&={\frac {F(z)+F(-z)}{2}}\\[4px]\sum _{n=0}^{\infty }f_{2n+1}z^{2n+1}&={\frac {F(z)-F(-z)}{2}}.\end{aligned}}}$$

De manera más general, supongamos que a ≥ 3 y que ω _a = exp2 πi/adenota la aésima raíz primitiva de la unidad . Entonces, como aplicación de la transformada discreta de Fourier , tenemos la fórmula ^[13]

$${\displaystyle \sum _{n=0}^{\infty }f_{an+b}z^{an+b}={\frac {1}{a}}\sum _{m=0}^{a-1}\omega _{a}^{-mb}F\left(\omega _{a}^{m}z\right).}$$

Para números enteros m ≥ 1 , la identidad genera otra fórmula útil que proporciona progresiones aritméticas de piso algo invertidas (repitiendo efectivamente cada coeficiente m veces) ^[14]

$${\displaystyle \sum _{n=0}^{\infty }f_{\left\lfloor {\frac {n}{m}}\right\rfloor }z^{n}={\frac {1-z^{m}}{1-z}}F(z^{m})=\left(1+z+\cdots +z^{m-2}+z^{m-1}\right)F(z^{m}).}$$

P -secuencias recursivas y funciones generadoras holonómicas.

Definiciones

Una serie de potencias formal (o función) F ( z ) se dice que es holonómica si satisface una ecuación diferencial lineal de la forma ^[15]

$${\displaystyle c_{0}(z)F^{(r)}(z)+c_{1}(z)F^{(r-1)}(z)+\cdots +c_{r}(z)F(z)=0,}$$

donde los coeficientes c _i ( z ) están en el campo de funciones racionales, . De manera equivalente, es holonómico si el espacio vectorial abarcado por el conjunto de todas sus derivadas es de dimensión finita. ${\displaystyle \mathbb {C} (z)}$ ${\displaystyle F(z)}$ ${\displaystyle \mathbb {C} (z)}$

Dado que podemos borrar los denominadores si es necesario en la ecuación anterior, podemos suponer que las funciones c _i ( z ) son polinomios en z . Por tanto, podemos ver una condición equivalente de que una función generadora es holonómica si sus coeficientes satisfacen una P -recurrencia de la forma

$${\displaystyle {\widehat {c}}_{s}(n)f_{n+s}+{\widehat {c}}_{s-1}(n)f_{n+s-1}+\cdots +{\widehat {c}}_{0}(n)f_{n}=0,}$$

para todos los suficientemente grandes n ≥ n ₀ y donde los ĉ _i ( n ) son polinomios fijos de grado finito en n . En otras palabras, las propiedades de que una secuencia sea P -recursiva y tenga una función generadora holonómica son equivalentes. Las funciones holonómicas están cerradas bajo la operación del producto Hadamard ⊙ sobre funciones generadoras.

Ejemplos

Las funciones e ^z , log z , cos z , arcsin z , , la función dilogaritmo Li ₂ ( z ) , las funciones hipergeométricas generalizadas _p F _q (...; ...; z ) y las funciones definidas por la serie de potencias ${\displaystyle {\sqrt {1+z}}}$

$${\displaystyle \sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2}}}}$$

y los no convergentes

$${\displaystyle \sum _{n=0}^{\infty }n!\cdot z^{n}}$$

son todos holonómicos.

Ejemplos de secuencias P -recursivas con funciones generadoras holonómicas incluyen f _n ≔1/norte + 1 (^{2 norte}
_norte) y f _norte ≔2 ^norte/norte ² + 1, donde secuencias como y log n no son P -recursivas debido a la naturaleza de las singularidades en sus correspondientes funciones generadoras. De manera similar, funciones con infinitas singularidades como tan z , sec z y Γ( z ) no son funciones holonómicas. ${\displaystyle {\sqrt {n}}}$

Software para trabajar con secuencias P -recursivas y funciones generadoras holonómicas.

Las herramientas para procesar y trabajar con secuencias P -recursivas en Mathematica incluyen los paquetes de software proporcionados para uso no comercial en el sitio de software de combinatoria algorítmica de RISC Combinatorics Group. A pesar de ser en su mayoría de código cerrado, el paquete proporciona herramientas particularmente poderosas en este paquete de software Guesspara adivinar P -recurrencias para secuencias de entrada arbitrarias (útil para matemáticas experimentales y exploración) y el Sigmapaquete que es capaz de encontrar P-recurrencias para muchas sumas. y resolver soluciones en forma cerrada para P -recurrencias que involucran números armónicos generalizados . ^[16] Otros paquetes enumerados en este sitio RISC en particular están destinados a trabajar específicamente con funciones de generación holonómica.

Relación con la transformada de Fourier en tiempo discreto

Cuando la serie converge absolutamente ,

$${\displaystyle G\left(a_{n};e^{-i\omega }\right)=\sum _{n=0}^{\infty }a_{n}e^{-i\omega n}}$$

a ₀ , a ₁ , ...

Crecimiento asintótico de una secuencia.

En cálculo, a menudo la tasa de crecimiento de los coeficientes de una serie de potencias se puede utilizar para deducir un radio de convergencia para la serie de potencias. Lo contrario también puede ser válido; a menudo, el radio de convergencia de una función generadora se puede utilizar para deducir el crecimiento asintótico de la secuencia subyacente.

Por ejemplo, si una función generadora ordinaria G ( an ; x ) que tiene un radio de convergencia finito de _r se puede escribir como

$${\displaystyle G(a_{n};x)={\frac {A(x)+B(x)\left(1-{\frac {x}{r}}\right)^{-\beta }}{x^{\alpha }}}}$$

donde cada una de A ( x ) y B ( x ) es una función analítica para un radio de convergencia mayor que r (o es entera ), y donde B ( r ) ≠ 0 entonces

$${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}\sim {\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}}\right)^{n}={\frac {B(r)}{r^{\alpha }}}\left(\!\!{\binom {\beta }{n}}\!\!\right)\left({\frac {1}{r}}\right)^{n}\,,}$$

función gammacoeficiente binomialcoeficiente multiconjunto

_{A menudo ,} este enfoque se puede iterar para generar varios términos en una serie asintótica para n . En particular,

$${\displaystyle G\left(a_{n}-{\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}}\right)^{n};x\right)=G(a_{n};x)-{\frac {B(r)}{r^{\alpha }}}\left(1-{\frac {x}{r}}\right)^{-\beta }\,.}$$

El crecimiento asintótico de los coeficientes de esta función generadora puede buscarse mediante el hallazgo de A , B , α , β yr para describir la función generadora, como se indicó anteriormente .

Es posible un análisis asintótico similar para funciones generadoras exponenciales; con una función generadora exponencial, esun _{_}/norte !que crece según estas fórmulas asintóticas. Generalmente, si la función generadora de una secuencia menos la función generadora de una segunda secuencia tiene un radio de convergencia mayor que el radio de convergencia de las funciones generadoras individuales, entonces las dos secuencias tienen el mismo crecimiento asintótico.

Crecimiento asintótico de la secuencia de cuadrados.

Como se derivó anteriormente, la función generadora ordinaria para la secuencia de cuadrados es

$${\displaystyle G(n^{2};x)={\frac {x(x+1)}{(1-x)^{3}}}.}$$

Con r = 1 , α = −1 , β = 3 , A ( x ) = 0 y B ( x ) = x + 1 , podemos verificar que los cuadrados crecen como se esperaba, al igual que los cuadrados:

$${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {1+1}{1^{-1}\,\Gamma (3)}}\,n^{3-1}\left({\frac {1}{1}}\right)^{n}=n^{2}.}$$

Crecimiento asintótico de las cifras catalanas

La función generadora ordinaria para los números catalanes es

$${\displaystyle G(C_{n};x)={\frac {1-{\sqrt {1-4x}}}{2x}}.}$$

Con r =1/4, α = 1 , β = −1/2, A ( x ) =1/2, y B ( x ) = −1/2, podemos concluir que, para los números catalanes,

$${\displaystyle C_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {-{\frac {1}{2}}}{\left({\frac {1}{4}}\right)^{1}\Gamma \left(-{\frac {1}{2}}\right)}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\,{\frac {1}{4}}\,}}\right)^{n}={\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}.}$$

Funciones generadoras bivariadas y multivariadas

Se pueden definir funciones generadoras en varias variables para matrices con varios índices. Éstas se denominan funciones generadoras multivariadas o, a veces, funciones supergeneradoras . Para dos variables, a menudo se les llama funciones generadoras bivariadas .

Por ejemplo, dado que (1 + x ) ⁿ es la función generadora ordinaria de coeficientes binomiales para un n fijo , se puede solicitar una función generadora bivariada que genere los coeficientes binomiales (^nk
_{_}) para todo k y n . Para hacer esto, considere (1 + x ) ⁿ como una secuencia en n y encuentre la función generadora en y que tenga estos valores de secuencia como coeficientes. Dado que la función generadora ^de an es

$${\displaystyle {\frac {1}{1-ay}},}$$

la función generadora de los coeficientes binomiales es:

$${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}.}$$

Representación por fracciones continuas (fracciones J tipo Jacobi )

Definiciones

Las expansiones de fracciones continuas (formales) de tipo Jacobi y tipo Stieltjes ( fracciones J y fracciones S , respectivamente) cuyos h ésimos convergentes racionales representan series de potencias precisas de orden 2 h son otra forma de expresar las funciones generadoras ordinarias típicamente divergentes para muchas secuencias especiales de una y dos variables. La forma particular de las fracciones continuas de tipo Jacobi ( J -fracciones) se expande como en la siguiente ecuación y tiene las siguientes expansiones de series de potencias correspondientes con respecto a z para algunas secuencias de componentes específicas que dependen de la aplicación, {ab _i } y { c _i } , donde z ≠ 0 denota la variable formal en la segunda expansión de la serie de potencias que se muestra a continuación: ^[17]

$${\displaystyle {\begin{aligned}J^{[\infty ]}(z)&={\cfrac {1}{1-c_{1}z-{\cfrac {{\text{ab}}_{2}z^{2}}{1-c_{2}z-{\cfrac {{\text{ab}}_{3}z^{2}}{\ddots }}}}}}\\[4px]&=1+c_{1}z+\left({\text{ab}}_{2}+c_{1}^{2}\right)z^{2}+\left(2{\text{ab}}_{2}c_{1}+c_{1}^{3}+{\text{ab}}_{2}c_{2}\right)z^{3}+\cdots \end{aligned}}}$$

Los coeficientes de , denotados brevemente por j _n ≔ [ z ⁿ ] J ^[∞] ( z ) , en las ecuaciones anteriores corresponden a soluciones matriciales de las ecuaciones ${\displaystyle z^{n}}$

$${\displaystyle {\begin{bmatrix}k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\k_{0,3}&k_{1,3}&k_{2,3}&k_{3,3}&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}={\begin{bmatrix}k_{0,0}&0&0&0&\cdots \\k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}\cdot {\begin{bmatrix}c_{1}&1&0&0&\cdots \\{\text{ab}}_{2}&c_{2}&1&0&\cdots \\0&{\text{ab}}_{3}&c_{3}&1&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}},}$$

donde j ₀ ≡ k _0,0 = 1 , j _n = k _{0, n} para n ≥ 1 , k _{r , s} = 0 si r > s , y donde para todos los números enteros p , q ≥ 0 , tenemos una fórmula de suma relación dada por

$${\displaystyle j_{p+q}=k_{0,p}\cdot k_{0,q}+\sum _{i=1}^{\min(p,q)}{\text{ab}}_{2}\cdots {\text{ab}}_{i+1}\times k_{i,p}\cdot k_{i,q}.}$$

Propiedades de las h -ésimas funciones convergentes

Para h ≥ 0 (aunque en la práctica cuando h ≥ 2 ), podemos definir los h ésimos racionales convergentes a la infinita J -fracción, J ^[∞] ( z ) , expandida por

$${\displaystyle \operatorname {Conv} _{h}(z):={\frac {P_{h}(z)}{Q_{h}(z)}}=j_{0}+j_{1}z+\cdots +j_{2h-1}z^{2h-1}+\sum _{n=2h}^{\infty }{\widetilde {j}}_{h,n}z^{n}}$$

componente a través de las secuencias, P _h ( z ) y Q _h ( z ) , definidas recursivamente por

$${\displaystyle {\begin{aligned}P_{h}(z)&=(1-c_{h}z)P_{h-1}(z)-{\text{ab}}_{h}z^{2}P_{h-2}(z)+\delta _{h,1}\\Q_{h}(z)&=(1-c_{h}z)Q_{h-1}(z)-{\text{ab}}_{h}z^{2}Q_{h-2}(z)+(1-c_{1}z)\delta _{h,1}+\delta _{0,1}.\end{aligned}}}$$

Además, la racionalidad de la función convergente Conv _h ( z ) para todo h ≥ 2 implica ecuaciones en diferencias finitas adicionales y propiedades de congruencia satisfechas por la secuencia de j _n , y para M _h ≔ ab ₂ ⋯ ab _{h + 1} si h ‖ M _h entonces tenemos la congruencia

$${\displaystyle j_{n}\equiv [z^{n}]\operatorname {Conv} _{h}(z){\pmod {h}},}$$

para elecciones determinadas y no simbólicas de las secuencias de parámetros {ab _i } y { c _i } cuando h ≥ 2 , es decir, cuando estas secuencias no dependen implícitamente de un parámetro auxiliar como q , x o R como en el ejemplos contenidos en la siguiente tabla.

Ejemplos

La siguiente tabla proporciona ejemplos de fórmulas de forma cerrada para las secuencias componentes encontradas computacionalmente (y posteriormente demostradas como correctas en las referencias citadas ^[18] ) en varios casos especiales de las secuencias prescritas, j _n , generadas por las expansiones generales de J - fracciones definidas en el inciso primero. Aquí definimos 0 < | un |, | segundo |, | q | < 1 y los parámetros y x son indeterminados con respecto a estas expansiones, donde las secuencias prescritas enumeradas por las expansiones de estas J -fracciones se definen en términos del símbolo q -Pochhammer , el símbolo de Pochhammer y los coeficientes binomiales . ${\displaystyle R,\alpha \in \mathbb {Z} ^{+}}$

Los radios de convergencia de estas series correspondientes a la definición de las fracciones J de tipo Jacobi dadas anteriormente son en general diferentes de los de las correspondientes expansiones de series de potencias que definen las funciones generadoras ordinarias de estas secuencias.

Ejemplos

Las funciones generadoras para la secuencia de números cuadrados a _n = n ² son:

Función generadora ordinaria

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

Función generadora exponencial

$${\displaystyle \operatorname {EG} (n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}}$$

serie lamberto

Como ejemplo de una identidad de serie de Lambert que no se proporciona en el artículo principal , podemos mostrar que para | x |, | xq | < 1 tenemos eso ^[19]

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

donde tenemos la identidad del caso especial para la función generadora de la función divisora , d ( n ) ≡ σ ₀ ( n ) , dada por

$${\displaystyle \sum _{n=1}^{\infty }{\frac {x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {x^{n^{2}}\left(1+x^{n}\right)}{1-x^{n}}}.}$$

serie campana

$${\displaystyle \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}}}$$

Función generadora de series de Dirichlet

$${\displaystyle \operatorname {DG} \left(n^{2};s\right)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2),}$$

utilizando la función zeta de Riemann .

La secuencia a _k generada por una función generadora de series de Dirichlet (DGF) correspondiente a:

$${\displaystyle \operatorname {DG} (a_{k};s)=\zeta (s)^{m}}$$

donde ζ ( s ) es la función zeta de Riemann , tiene la función generadora ordinaria:

$${\displaystyle \sum _{k=1}^{k=n}a_{k}x^{k}=x+{\binom {m}{1}}\sum _{2\leq a\leq n}x^{a}+{\binom {m}{2}}{\underset {ab\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }}}x^{ab}+{\binom {m}{3}}{\underset {abc\leq n}{\sum _{a=2}^{\infty }\sum _{c=2}^{\infty }\sum _{b=2}^{\infty }}}x^{abc}+{\binom {m}{4}}{\underset {abcd\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }}}x^{abcd}+\cdots }$$

Funciones generadoras multivariadas

Las funciones generadoras multivariadas surgen en la práctica cuando se calcula el número de tablas de contingencia de números enteros no negativos con totales de filas y columnas específicos. Supongamos que la tabla tiene r filas yc columnas ; las sumas de las filas son t ₁ , t ₂ ... t _r y las sumas de las columnas son s ₁ , s ₂ ... s _c . Entonces, según IJ Good , ^[20] el número de dichas tablas es el coeficiente de

$${\displaystyle x_{1}^{t_{1}}\cdots x_{r}^{t_{r}}y_{1}^{s_{1}}\cdots y_{c}^{s_{c}}}$$

en

$${\displaystyle \prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}.}$$

En el caso bivariado, ejemplos de suma doble no polinómica de las llamadas funciones generadoras " dobles " o " súper " de la forma

$${\displaystyle G(w,z):=\sum _{m,n\geq 0}g_{m,n}w^{m}z^{n}}$$

Incluye las siguientes funciones generadoras de dos variables para los coeficientes binomiales , los números de Stirling y los números de Euler : ^[21]

$${\displaystyle {\begin{aligned}e^{z+wz}&=\sum _{m,n\geq 0}{\binom {n}{m}}w^{m}{\frac {z^{n}}{n!}}\\[4px]e^{w(e^{z}-1)}&=\sum _{m,n\geq 0}{\begin{Bmatrix}n\\m\end{Bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1}{(1-z)^{w}}}&=\sum _{m,n\geq 0}{\begin{bmatrix}n\\m\end{bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1-w}{e^{(w-1)z}-w}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}n\\m\end{matrix}}\right\rangle w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {e^{w}-e^{z}}{we^{z}-ze^{w}}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}m+n+1\\m\end{matrix}}\right\rangle {\frac {w^{m}z^{n}}{(m+n+1)!}}.\end{aligned}}}$$

Aplicaciones

Varias técnicas: evaluación de sumas y resolución de otros problemas con funciones generadoras

Ejemplo 1: una fórmula para sumas de números armónicos

Las funciones generadoras nos brindan varios métodos para manipular sumas y establecer identidades entre sumas.

El caso más simple ocurre cuando s _n = Σ^norte
_{k = 0} ak . _{_} Entonces sabemos que S ( z ) =A ( z )/1- zpara las correspondientes funciones generadoras ordinarias.

Por ejemplo, podemos manipular

$${\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}\,,}$$

H _k = 1 +1/2+ ⋯ +1/knúmeros armónicos

$${\displaystyle H(z)=\sum _{n=1}^{\infty }{H_{n}z^{n}}}$$

$${\displaystyle H(z)={\frac {1}{1-z}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,,}$$

$${\displaystyle S(z)=\sum _{n=1}^{\infty }{s_{n}z^{n}}={\frac {1}{(1-z)^{2}}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,.}$$

Usando

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

$${\displaystyle s_{n}=\sum _{k=1}^{n}{\frac {n+1-k}{k}}=(n+1)H_{n}-n\,,}$$

$${\displaystyle \sum _{k=1}^{n}{H_{k}}=(n+1)(H_{n+1}-1)\,.}$$

Ejemplo 2: sumas de coeficientes binomiales modificados y transformación binomial

Como otro ejemplo del uso de funciones generadoras para relacionar secuencias y manipular sumas, para una secuencia arbitraria ⟨ f _n ⟩ definimos las dos secuencias de sumas

$${\displaystyle {\begin{aligned}s_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}f_{m}3^{n-m}\\[4px]{\tilde {s}}_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}(m+1)(m+2)(m+3)f_{m}3^{n-m}\,,\end{aligned}}}$$

n ≥ 0

Primero, usamos la transformada binomial para escribir la función generadora de la primera suma como

$${\displaystyle S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}}\right).}$$

Dado que la función generadora de la secuencia ⟨ ( n + 1)( n + 2)( n + 3) f _n ⟩ está dada por

$${\displaystyle 6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z)}$$

$${\displaystyle {\tilde {S}}(z)={\frac {6}{(1-3z)}}F\left({\frac {z}{1-3z}}\right)+{\frac {18z}{(1-3z)^{2}}}F'\left({\frac {z}{1-3z}}\right)+{\frac {9z^{2}}{(1-3z)^{3}}}F''\left({\frac {z}{1-3z}}\right)+{\frac {z^{3}}{(1-3z)^{4}}}F'''\left({\frac {z}{1-3z}}\right).}$$

En particular, podemos escribir esta función generadora de suma modificada en la forma de

$${\displaystyle a(z)\cdot S(z)+b(z)\cdot zS'(z)+c(z)\cdot z^{2}S''(z)+d(z)\cdot z^{3}S'''(z),}$$

a ( z ) = 6(1 − 3 z ) ³b ( z ) = 18(1 − 3 z ) ³c ( z ) = 9(1 − 3 z ) ³d ( z ) = ( 1 - 3 z ) ³(1 - 3 z ) ³ = 1 - 9 z + 27 z ² - 27 z ³

Finalmente, se deduce que podemos expresar las segundas sumas a través de las primeras sumas de la siguiente forma:

$${\displaystyle {\begin{aligned}{\tilde {s}}_{n}&=[z^{n}]\left(6(1-3z)^{3}\sum _{n=0}^{\infty }s_{n}z^{n}+18(1-3z)^{3}\sum _{n=0}^{\infty }ns_{n}z^{n}+9(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)s_{n}z^{n}+(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)(n-2)s_{n}z^{n}\right)\\[4px]&=(n+1)(n+2)(n+3)s_{n}-9n(n+1)(n+2)s_{n-1}+27(n-1)n(n+1)s_{n-2}-(n-2)(n-1)ns_{n-3}.\end{aligned}}}$$

Ejemplo 3: Generar funciones para secuencias mutuamente recursivas

En este ejemplo, reformulamos un ejemplo de función generadora dado en la Sección 7.3 de Matemáticas Concretas (ver también la Sección 7.1 de la misma referencia para ver bonitas imágenes de series de funciones generadoras). En particular, supongamos que buscamos el número total de formas (denotadas U _n ) para colocar en mosaico un rectángulo de 3 por n con piezas de dominó de 2 por 1 sin marcar. Definamos la secuencia auxiliar, V _n , como el número de formas de cubrir una sección de rectángulo menos esquinas de 3 por n del rectángulo completo. Buscamos utilizar estas definiciones para dar una fórmula de forma cerrada para U _n sin desglosar más esta definición para manejar los casos de dominó vertical versus horizontal. Observe que las funciones generadoras ordinarias para nuestras dos secuencias corresponden a la serie

$${\displaystyle {\begin{aligned}U(z)=1+3z^{2}+11z^{4}+41z^{6}+\cdots ,\\V(z)=z+4z^{3}+15z^{5}+56z^{7}+\cdots .\end{aligned}}}$$

Si consideramos las posibles configuraciones que se pueden dar a partir del borde izquierdo del rectángulo de 3 por n , podemos expresar las siguientes relaciones de recurrencia mutuamente dependientes o recursivas para nuestras dos secuencias cuando n ≥ 2 se define como arriba donde U ₀ = 1 , U ₁ = 0 , V ₀ = 0 y V ₁ = 1 :

$${\displaystyle {\begin{aligned}U_{n}&=2V_{n-1}+U_{n-2}\\V_{n}&=U_{n-1}+V_{n-2}.\end{aligned}}}$$

Como tenemos eso para todos los números enteros m ≥ 0 , las funciones generadoras de índice desplazado satisfacen ^{[nota 1]}

$${\displaystyle z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\,,}$$

$${\displaystyle {\begin{aligned}U(z)&=2zV(z)+z^{2}U(z)+1\\V(z)&=zU(z)+z^{2}V(z)={\frac {z}{1-z^{2}}}U(z),\end{aligned}}}$$

$${\displaystyle U(z)={\frac {1-z^{2}}{1-4z^{2}+z^{4}}}={\frac {1}{3-{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2+{\sqrt {3}}\right)z^{2}}}+{\frac {1}{3+{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2-{\sqrt {3}}\right)z^{2}}}.}$$

Así, al realizar simplificaciones algebraicas a la secuencia resultante de las segundas expansiones en fracciones parciales de la función generadora en la ecuación anterior, encontramos que U _{2 n + 1} ≡ 0 y que

$${\displaystyle U_{2n}=\left\lceil {\frac {\left(2+{\sqrt {3}}\right)^{n}}{3-{\sqrt {3}}}}\right\rceil \,,}$$

norte ≥ 0recurrencianúmeros de Fibonacciracionalidad. funciones

Convolución (productos Cauchy)

Una convolución discreta de los términos en dos series de potencias formales convierte un producto de funciones generadoras en una función generadora que enumera una suma convolucionada de los términos de la secuencia original (ver Producto de Cauchy ).

1. Considere que A ( z ) y B ( z ) son funciones generadoras ordinarias.
   $${\displaystyle C(z)=A(z)B(z)\Leftrightarrow [z^{n}]C(z)=\sum _{k=0}^{n}{a_{k}b_{n-k}}}$$
2. Considere que A ( z ) y B ( z ) son funciones generadoras exponenciales.
   $${\displaystyle C(z)=A(z)B(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}}\right]C(z)=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{n-k}}$$
3. Considere la secuencia triplemente convolucionada resultante del producto de tres funciones generadoras ordinarias
   $${\displaystyle C(z)=F(z)G(z)H(z)\Leftrightarrow [z^{n}]C(z)=\sum _{j+k+l=n}f_{j}g_{k}h_{l}}$$
4. Considere la convolución m veces de una secuencia consigo misma para algún entero positivo m ≥ 1 (consulte el siguiente ejemplo para una aplicación)
   $${\displaystyle C(z)=G(z)^{m}\Leftrightarrow [z^{n}]C(z)=\sum _{k_{1}+k_{2}+\cdots +k_{m}=n}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}}$$

La multiplicación de funciones generadoras, o la convolución de sus secuencias subyacentes, puede corresponder a una noción de eventos independientes en ciertos escenarios de conteo y probabilidad. Por ejemplo, si adoptamos la convención de notación de que la función generadora de probabilidad , o pgf , de una variable aleatoria Z se denota por G _Z ( z ) , entonces podemos demostrar que para dos variables aleatorias cualesquiera ^[22]

$${\displaystyle G_{X+Y}(z)=G_{X}(z)G_{Y}(z)\,,}$$

XYn ≥ 0

$${\displaystyle C(z)={\frac {1}{1-z}}{\frac {1}{1-z^{5}}}{\frac {1}{1-z^{10}}}{\frac {1}{1-z^{25}}}{\frac {1}{1-z^{50}}},}$$

nfunción de particiónq -Símbolo de Pochhammer

$${\displaystyle \prod _{n=1}^{\infty }\left(1-z^{n}\right)^{-1}\,.}$$

Ejemplo: La función generadora de los números catalanes.

Un ejemplo en el que las convoluciones de funciones generadoras son útiles nos permite resolver una función de forma cerrada específica que representa la función generadora ordinaria para los números catalanes , C _n . En particular, esta secuencia tiene la interpretación combinatoria como el número de formas de insertar paréntesis en el producto x ₀ · x ₁ ·⋯· x _n de modo que el orden de multiplicación esté completamente especificado. Por ejemplo, C ₂ = 2 que corresponde a las dos expresiones x ₀ · ( x ₁ · x ₂ ) y ( x ₀ · x ₁ ) · x ₂ . De ello se deduce que la secuencia satisface una relación de recurrencia dada por

$${\displaystyle C_{n}=\sum _{k=0}^{n-1}C_{k}C_{n-1-k}+\delta _{n,0}=C_{0}C_{n-1}+C_{1}C_{n-2}+\cdots +C_{n-1}C_{0}+\delta _{n,0}\,,\quad n\geq 0\,,}$$

C ( z )

$${\displaystyle C(z)=z\cdot C(z)^{2}+1\,.}$$

Dado que C (0) = 1 ≠ ∞ , llegamos a una fórmula para esta función generadora dada por

$${\displaystyle C(z)={\frac {1-{\sqrt {1-4z}}}{2z}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}z^{n}\,.}$$

Tenga en cuenta que la primera ecuación que implícitamente define C ( z ) arriba implica que

$${\displaystyle C(z)={\frac {1}{1-z\cdot C(z)}}\,,}$$

Ejemplo: árboles de expansión de abanicos y convoluciones de convoluciones.

Un abanico de orden n se define como un gráfico en los vértices {0, 1, ..., n } con 2 n − 1 aristas conectadas de acuerdo con las siguientes reglas: El vértice 0 está conectado por una única arista a cada uno de los otros n vértices, y el vértice está conectado por un solo borde al siguiente vértice k + 1 para todo 1 ≤ k < n . ^[23] Hay un ventilador de orden uno, tres ventiladores de orden dos, ocho ventiladores de orden tres, y así sucesivamente. Un árbol de expansión es un subgrafo de un gráfico que contiene todos los vértices originales y que contiene suficientes aristas para conectar este subgrafo, pero no tantas aristas como para que haya un ciclo en el subgrafo. Preguntamos cuántos árboles generadores f _n de un abanico de orden n son posibles para cada n ≥ 1 . ${\displaystyle k}$

Como observación, podemos abordar la cuestión contando el número de formas de unir conjuntos de vértices adyacentes. Por ejemplo, cuando n = 4 , tenemos que f ₄ = 4 + 3 · 1 + 2 · 2 + 1 · 3 + 2 · 1 · 1 + 1 · 2 · 1 + 1 · 1 · 2 + 1 · 1 · 1 · 1 = 21 , que es una suma de las m convoluciones de la secuencia g _n = n = [ z ⁿ ]z/(1 − z ) ²para metro ≔ 1, 2, 3, 4 . De manera más general, podemos escribir una fórmula para esta secuencia como

$${\displaystyle f_{n}=\sum _{m>0}\sum _{\scriptstyle k_{1}+k_{2}+\cdots +k_{m}=n \atop \scriptstyle k_{1},k_{2},\ldots ,k_{m}>0}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}\,,}$$

$${\displaystyle F(z)=G(z)+G(z)^{2}+G(z)^{3}+\cdots ={\frac {G(z)}{1-G(z)}}={\frac {z}{(1-z)^{2}-z}}={\frac {z}{1-3z+z^{2}}}\,,}$$

expansión en fracción parcial

Funciones generadoras implícitas y fórmula de inversión de Lagrange

A menudo nos encontramos con funciones generadoras especificadas por una ecuación funcional, en lugar de una especificación explícita. Por ejemplo, la función generadora T(z) para el número de árboles binarios en n nodos (hojas incluidas) satisface

$${\displaystyle T(z)=z\left(1+T(z)^{2}\right)}$$

El teorema de inversión de Lagrange es una herramienta que se utiliza para evaluar explícitamente soluciones a este tipo de ecuaciones.

Fórmula de inversión de Lagrange  :  sea una serie de potencias formal con un término constante distinto de cero. Entonces la ecuación funcional ${\textstyle \phi (z)\in C[[z]]}$

$${\displaystyle T(z)=z\phi (T(z))}$$

admite una solución única en , que satisface ${\textstyle T(z)\in C[[z]]}$

${\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(\phi (z))^{n}}$

donde la notación devuelve el coeficiente de in . ${\displaystyle [z^{n}]F(z)}$ ${\displaystyle z^{n}}$ ${\displaystyle F(z)}$

Aplicando el teorema anterior a nuestra ecuación funcional se obtiene (con ): ${\textstyle \phi (z)=1+z^{2}}$

$${\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}}$$

A través de la expansión del teorema del binomio, incluso para , la fórmula devuelve . Esto es de esperar, ya que se puede demostrar que el número de hojas de un árbol binario es uno más que el número de sus nodos internos, por lo que la suma total siempre debe ser un número impar. Por impar , sin embargo, obtenemos ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$

${\displaystyle [z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}={\frac {1}{n}}{\dbinom {n}{\frac {n+1}{2}}}}$

La expresión se vuelve mucho más clara si dejamos que sea el número de nodos internos: ahora la expresión se convierte en el ^enésimo número catalán. ${\displaystyle n}$ ${\displaystyle n}$

Introducción de un parámetro gratuito (método del aceite de serpiente)

A veces la suma s _n es complicada y no siempre es fácil de evaluar. El método "Parámetro libre" es otro método (llamado "aceite de serpiente" por H. Wilf) para evaluar estas sumas.

Ambos métodos discutidos hasta ahora tienen n como límite en la sumatoria. Cuando n no aparece explícitamente en la suma, podemos considerar n como un parámetro "libre" y tratar a s _n como un coeficiente de F ( z ) = Σ s _n z ⁿ , cambiar el orden de las sumas en n y k , e intenta calcular la suma interna.

Por ejemplo, si queremos calcular

$${\displaystyle s_{n}=\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\,,\quad m,n\in \mathbb {N} _{0}\,,}$$

n

$${\displaystyle F(z)=\sum _{n=0}^{\infty }{\left(\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\right)}z^{n}\,.}$$

La suma intercambiable ("aceite de serpiente") da

$${\displaystyle F(z)=\sum _{k=0}^{\infty }{{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-k}}\sum _{n=0}^{\infty }{{\binom {n+k}{m+2k}}z^{n+k}}\,.}$$

Ahora la suma interna esz ^{m + 2 k}/(1 − z ) ^{m + 2 k + 1}. De este modo

$${\displaystyle {\begin{aligned}F(z)&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-z}{(1-z)^{2}}}\right)^{k}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{C_{k}\left({\frac {-z}{(1-z)^{2}}}\right)^{k}}&{\text{where }}C_{k}=k{\text{th Catalan number}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}{\frac {1-{\sqrt {1+{\frac {4z}{(1-z)^{2}}}}}}{\frac {-2z}{(1-z)^{2}}}}\\[4px]&={\frac {-z^{m-1}}{2(1-z)^{m-1}}}\left(1-{\frac {1+z}{1-z}}\right)\\[4px]&={\frac {z^{m}}{(1-z)^{m}}}=z{\frac {z^{m-1}}{(1-z)^{m}}}\,.\end{aligned}}}$$

Entonces obtenemos

$${\displaystyle s_{n}={\begin{cases}\displaystyle {\binom {n-1}{m-1}}&{\text{for }}m\geq 1\,,\\{}[n=0]&{\text{for }}m=0\,.\end{cases}}}$$

Es instructivo volver a utilizar el mismo método para la suma, pero esta vez tome m como parámetro libre en lugar de n . Así establecemos

$${\displaystyle G(z)=\sum _{m=0}^{\infty }\left(\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}\right)z^{m}\,.}$$

La suma intercambiable ("aceite de serpiente") da

$${\displaystyle G(z)=\sum _{k=0}^{\infty }{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-2k}\sum _{m=0}^{\infty }{\binom {n+k}{m+2k}}z^{m+2k}\,.}$$

Ahora la suma interna es (1 + z ) ^{n + k} . De este modo

$${\displaystyle {\begin{aligned}G(z)&=(1+z)^{n}\sum _{k=0}^{\infty }{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-(1+z)}{z^{2}}}\right)^{k}\\[4px]&=(1+z)^{n}\sum _{k=0}^{\infty }C_{k}\,\left({\frac {-(1+z)}{z^{2}}}\right)^{k}&{\text{where }}C_{k}=k{\text{th Catalan number}}\\[4px]&=(1+z)^{n}\,{\frac {1-{\sqrt {1+{\frac {4(1+z)}{z^{2}}}}}}{\frac {-2(1+z)}{z^{2}}}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z{\sqrt {z^{2}+4+4z}}}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z(z+2)}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {-2z}{-2(1+z)}}=z(1+z)^{n-1}\,.\end{aligned}}}$$

Así obtenemos

$${\displaystyle s_{n}=\left[z^{m}\right]z(1+z)^{n-1}=\left[z^{m-1}\right](1+z)^{n-1}={\binom {n-1}{m-1}}\,,}$$

m ≥ 1

Las funciones generadoras prueban congruencias

Decimos que dos funciones generadoras (series de potencias) son congruentes módulo m , escritas A ( z ) ≡ B ( z ) (mod m ) si sus coeficientes son congruentes módulo m para todo n ≥ 0 , es decir, a _n ≡ b _n ( mod m ) para todos los casos relevantes de los números enteros n (tenga en cuenta que no necesitamos asumir que m es un número entero aquí; es muy posible que tenga un valor polinomial en algún x indeterminado , por ejemplo). Si la función generadora del lado derecho "más simple", B ( z ) , es una función racional de z , entonces la forma de esta secuencia sugiere que la secuencia es eventualmente periódica módulo fijo casos particulares de m ≥ 2 con valores enteros . Por ejemplo, podemos demostrar que los números de Euler ,

$${\displaystyle \langle E_{n}\rangle =\langle 1,1,5,61,1385,\ldots \rangle \longmapsto \langle 1,1,2,1,2,1,2,\ldots \rangle {\pmod {3}}\,,}$$

^[24]

$${\displaystyle \sum _{n=0}^{\infty }E_{n}z^{n}={\frac {1-z^{2}}{1+z^{2}}}{\pmod {3}}\,.}$$

Un método útil para obtener congruencias para secuencias enumeradas mediante funciones generadoras especiales módulo cualquier número entero (es decir, no sólo potencias primas p ^k ) se proporciona en la sección anterior sobre representaciones de fracciones continuas de funciones generadoras ordinarias (incluso no convergentes) mediante J -fracciones. . Citamos un resultado particular relacionado con la generación de series expandidas a través de una representación por fracción continua de las Conferencias de Lando sobre Generación de Funciones de la siguiente manera:

Teorema: congruencias para series generadas por expansiones de fracciones continuas  .  Supongamos que la función generadora A ( z ) está representada por una fracción continua infinita de la forma

$${\displaystyle A(z)={\cfrac {1}{1-c_{1}z-{\cfrac {p_{1}z^{2}}{1-c_{2}z-{\cfrac {p_{2}z^{2}}{1-c_{3}z-{\ddots }}}}}}}}$$

y que A _p ( z ) denota el p ésimo convergente a esta expansión fraccionaria continua definida tal que _{an =} [ z n ^] Ap ( z ) para todo 0 ≤ n < 2 p . Entonces:

1. la función A _p ( z ) es racional para todo p ≥ 2 donde asumimos que uno de los criterios de divisibilidad de p | p ₁ , p ₁ p ₂ , p ₁ p ₂ p ₃ se cumple, es decir, p | p ₁ p ₂ ⋯ p _k para algunos k ≥ 1 ; y
2. si el número entero p divide el producto p ₁ p ₂ ⋯ p _k , entonces tenemos A ( z ) ≡ A _k ( z ) (mod p ) .

Las funciones generadoras también tienen otros usos para demostrar congruencias de sus coeficientes. Citamos los siguientes dos ejemplos específicos que derivan congruencias de casos especiales para los números de Stirling del primer tipo y para la función de partición p ( n ) que muestran la versatilidad de generar funciones para abordar problemas que involucran secuencias de números enteros .

Los números de Stirling módulo enteros pequeños

El artículo principal sobre los números de Stirling generados por los productos finitos.

$${\displaystyle S_{n}(x):=\sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}=x(x+1)(x+2)\cdots (x+n-1)\,,\quad n\geq 1\,,}$$

proporciona una descripción general de las congruencias de estos números derivadas estrictamente de las propiedades de su función generadora, como en la Sección 4.6 de la referencia común de Wilf Generatingfunctionology . Repetimos el argumento básico y notamos que cuando se reduce el módulo 2, cada una de estas funciones generadoras de productos finitos satisface

$${\displaystyle S_{n}(x)=[x(x+1)]\cdot [x(x+1)]\cdots =x^{\left\lceil {\frac {n}{2}}\right\rceil }(x+1)^{\left\lfloor {\frac {n}{2}}\right\rfloor }\,,}$$

lo que implica que la paridad de estos números de Stirling coincide con la del coeficiente binomial

$${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}\equiv {\binom {\left\lfloor {\frac {n}{2}}\right\rfloor }{k-\left\lceil {\frac {n}{2}}\right\rceil }}{\pmod {2}}\,,}$$

y en consecuencia muestra que [^nk
_{_}] es par siempre que k < ⌊norte/2⌋ .

De manera similar, podemos reducir los productos del lado derecho que definen las funciones generadoras de números de Stirling módulo 3 para obtener expresiones ligeramente más complicadas siempre que

$${\displaystyle {\begin{aligned}{\begin{bmatrix}n\\m\end{bmatrix}}&\equiv [x^{m}]\left(x^{\left\lceil {\frac {n}{3}}\right\rceil }(x+1)^{\left\lceil {\frac {n-1}{3}}\right\rceil }(x+2)^{\left\lfloor {\frac {n}{3}}\right\rfloor }\right)&&{\pmod {3}}\\&\equiv \sum _{k=0}^{m}{\begin{pmatrix}\left\lceil {\frac {n-1}{3}}\right\rceil \\k\end{pmatrix}}{\begin{pmatrix}\left\lfloor {\frac {n}{3}}\right\rfloor \\m-k-\left\lceil {\frac {n}{3}}\right\rceil \end{pmatrix}}\times 2^{\left\lceil {\frac {n}{3}}\right\rceil +\left\lfloor {\frac {n}{3}}\right\rfloor -(m-k)}&&{\pmod {3}}\,.\end{aligned}}}$$

Congruencias para la función de partición

En este ejemplo, incorporamos parte de la maquinaria de productos infinitos cuyas expansiones en series de potencias generan las expansiones de muchas funciones especiales y enumeran funciones de partición. En particular, recordamos que la función de partición p ( n ) se genera por el producto infinito recíproco q -símbolo de Pochhammer (o producto z -Pochhammer, según sea el caso) dado por

$${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)z^{n}&={\frac {1}{\left(1-z\right)\left(1-z^{2}\right)\left(1-z^{3}\right)\cdots }}\\[4pt]&=1+z+2z^{2}+3z^{3}+5z^{4}+7z^{5}+11z^{6}+\cdots .\end{aligned}}}$$

Esta función de partición satisface muchas propiedades de congruencia conocidas , que incluyen en particular los siguientes resultados, aunque todavía hay muchas preguntas abiertas sobre las formas de congruencias enteras relacionadas para la función: ^[25]

$${\displaystyle {\begin{aligned}p(5m+4)&\equiv 0{\pmod {5}}\\p(7m+5)&\equiv 0{\pmod {7}}\\p(11m+6)&\equiv 0{\pmod {11}}\\p(25m+24)&\equiv 0{\pmod {5^{2}}}\,.\end{aligned}}}$$

Mostramos cómo utilizar funciones generadoras y manipulaciones de congruencias para series de potencias formales para dar una prueba altamente elemental de la primera de estas congruencias enumeradas anteriormente.

Primero, observamos que en la función generadora de coeficientes binomiales

$${\displaystyle {\frac {1}{(1-z)^{5}}}=\sum _{i=0}^{\infty }{\binom {4+i}{4}}z^{i}\,,}$$

1, z ⁵ , z ¹⁰ , ...

$${\displaystyle {\frac {1}{(1-z)^{5}}}\equiv {\frac {1}{1-z^{5}}}{\pmod {5}}\,,}$$

$${\displaystyle {\frac {1-z^{5}}{(1-z)^{5}}}\equiv 1{\pmod {5}}\,.}$$

$${\displaystyle {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\left(1-z^{15}\right)\cdots }{\left((1-z)\left(1-z^{2}\right)\left(1-z^{3}\right)\cdots \right)^{5}}}\equiv 1{\pmod {5}}\,.}$$

Usando las expansiones de productos infinitos de

$${\displaystyle z\cdot {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{\left(1-z\right)\left(1-z^{2}\right)\cdots }}=z\cdot \left((1-z)\left(1-z^{2}\right)\cdots \right)^{4}\times {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{\left(\left(1-z\right)\left(1-z^{2}\right)\cdots \right)^{5}}}\,,}$$

z ^{5 m + 5}z · ((1 − z )(1 − z ² )⋯) ⁴m^[26]

$${\displaystyle {\begin{aligned}\sum _{n=1}^{\infty }p(n-1)z^{n}&={\frac {z}{(1-z)\left(1-z^{2}\right)\cdots }}\\[6px]&=z\cdot {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{(1-z)\left(1-z^{2}\right)\cdots }}\times \left(1+z^{5}+z^{10}+\cdots \right)\left(1+z^{10}+z^{20}+\cdots \right)\cdots \end{aligned}}}$$

z ^{5 m + 5}p (5 m + 4) ≡ 0 (mod 5)m ≥ 0

Transformaciones de funciones generadoras.

Hay una serie de transformaciones de funciones generadoras que proporcionan otras aplicaciones (consulte el artículo principal ). Una transformación de la función generadora ordinaria (OGF) de una secuencia proporciona un método para convertir la función generadora de una secuencia en una función generadora que enumera otra. Estas transformaciones generalmente involucran fórmulas integrales que involucran una secuencia OGF (ver transformaciones integrales ) o sumas ponderadas sobre las derivadas de orden superior de estas funciones (ver transformaciones derivadas ).

Las transformaciones de funciones generadoras pueden entrar en juego cuando buscamos expresar una función generadora para las sumas

$${\displaystyle s_{n}:=\sum _{m=0}^{n}{\binom {n}{m}}C_{n,m}a_{m},}$$

en la forma de S ( z ) = g ( z ) A ( f ( z )) que involucra la función generadora de secuencia original. Por ejemplo, si las sumas son

$${\displaystyle s_{n}:=\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}a_{k}\,}$$

^[27]

$${\displaystyle S(z)={\frac {z^{m}}{(1-z)^{m+1}}}A\left({\frac {z}{(1-z)^{2}}}\right)}$$

transformada binomialtransformada de Stirling

También existen fórmulas integrales para convertir entre OGF, F ( z ) de una secuencia y su función generadora exponencial, o EGF, F̂ ( z ) , y viceversa dada por

$${\displaystyle {\begin{aligned}F(z)&=\int _{0}^{\infty }{\hat {F}}(tz)e^{-t}\,dt\,,\\[4px]{\hat {F}}(z)&={\frac {1}{2\pi }}\int _{-\pi }^{\pi }F\left(ze^{-i\vartheta }\right)e^{e^{i\vartheta }}\,d\vartheta \,,\end{aligned}}}$$

siempre que estas integrales converjan para valores apropiados de z .

Otras aplicaciones

Las funciones generadoras se utilizan para:

• Encuentre una fórmula cerrada para una secuencia dada en una relación de recurrencia. Por ejemplo, considere los números de Fibonacci .
• Encuentre relaciones de recurrencia para secuencias; la forma de una función generadora puede sugerir una fórmula de recurrencia.
• Encuentre relaciones entre secuencias: si las funciones generadoras de dos secuencias tienen una forma similar, entonces las secuencias mismas pueden estar relacionadas.
• Explora el comportamiento asintótico de secuencias.
• Demostrar identidades que involucran secuencias.
• Resolver problemas de enumeración en combinatoria y codificar sus soluciones. Los polinomios de torre son un ejemplo de aplicación en combinatoria.
• Evaluar sumas infinitas.

Otras funciones generadoras

Ejemplos

Ejemplos de secuencias polinomiales generadas por funciones generadoras más complejas incluyen:

• Polinomios de apelación
• Polinomios de Chebyshev
• Polinomios de diferencia
• Polinomios de Appell generalizados
• q -polinomios en diferencias

Otras secuencias generadas por funciones generadoras más complejas:

• Funciones generadoras exponenciales dobles. Por ejemplo: Matriz de Aitken: Triángulo de números
• Productos de Hadamard de funciones generadoras y funciones generadoras diagonales, y sus correspondientes transformaciones integrales

Polinomios de convolución

El artículo de Knuth titulado " Polinomios de convolución " ^[28] define una clase generalizada de secuencias de polinomios de convolución por sus funciones generadoras especiales de la forma

$${\displaystyle F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n},}$$

FF (0) = 1

Decimos que una familia de polinomios, f ₀ , f ₁ , f ₂ , ... , forma una familia de convolución si grados f _n ≤ n y si la siguiente condición de convolución se cumple para todo x , y y para todo n ≥ 0 :

$${\displaystyle f_{n}(x+y)=f_{n}(x)f_{0}(y)+f_{n-1}(x)f_{1}(y)+\cdots +f_{1}(x)f_{n-1}(y)+f_{0}(x)f_{n}(y).}$$

Vemos que para familias de convolución no idénticamente cero, esta definición equivale a requerir que la secuencia tenga una función generadora ordinaria de la primera forma dada anteriormente.

Una secuencia de polinomios de convolución definida en la notación anterior tiene las siguientes propiedades:

• La secuencia n ! · f _n ( x ) es de tipo binomial
• Los valores especiales de la secuencia incluyen f _n (1) = [ z ⁿ ] F ( z ) y f _n (0) = δ _{n ,0} , y
• Para arbitrarios (fijos) , estos polinomios satisfacen fórmulas de convolución de la forma ${\displaystyle x,y,t\in \mathbb {C} }$

$${\displaystyle {\begin{aligned}f_{n}(x+y)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(y)\\f_{n}(2x)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(x)\\xnf_{n}(x+y)&=(x+y)\sum _{k=0}^{n}kf_{k}(x)f_{n-k}(y)\\{\frac {(x+y)f_{n}(x+y+tn)}{x+y+tn}}&=\sum _{k=0}^{n}{\frac {xf_{k}(x+tk)}{x+tk}}{\frac {yf_{n-k}(y+t(n-k))}{y+t(n-k)}}.\end{aligned}}}$$

Para un parámetro fijo distinto de cero , hemos modificado las funciones generadoras para estas secuencias polinómicas de convolución dadas por ${\displaystyle t\in \mathbb {C} }$

$${\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n}\right]{\mathcal {F}}_{t}(z)^{x},}$$

𝓕 _t ( z )ecuación funcional𝓕 _t ( z ) = F ( x 𝓕 _t ( z ) ^t )⟨ f _n ( x ) ⟩⟨ g _n ( x ) ⟩F ( z ) ^xG ( z ) ^xt

$${\displaystyle \left[z^{n}\right]\left(G(z)F\left(zG(z)^{t}\right)\right)^{x}=\sum _{k=0}^{n}F_{k}(x)G_{n-k}(x+tk).}$$

Ejemplos de secuencias polinómicas de convolución incluyen la serie de potencias binomiales , 𝓑 _t ( z ) = 1 + z 𝓑 _t ( z ) ^t , los llamados polinomios de árbol , los números de Bell , B ( n ) , los polinomios de Laguerre y la convolución de Stirling. polinomios .

Tablas de funciones generadoras especiales.

Aquí se encuentra una lista inicial de series matemáticas especiales . En las secciones 5.4 y 7.4 de Concrete Mathematics y en la sección 2.5 de Wilf's Generatingfunctionology se encuentran varias funciones generadoras de secuencias útiles y especiales . Otras funciones generadoras especiales de interés incluyen las entradas de la siguiente tabla, que de ninguna manera está completa. ^[29]

Historia

George Pólya escribe en Matemáticas y razonamiento plausible :

El nombre de "función generadora" se debe a Laplace . Sin embargo, sin darle un nombre, Euler utilizó el recurso de generar funciones mucho antes que Laplace [...]. Aplicó esta herramienta matemática a varios problemas de Análisis Combinatorio y Teoría de Números .

Ver también

• Función generadora de momentos
• Función generadora de probabilidad
• Generando transformación de función
• Teorema de reciprocidad de Stanley
• Aplicaciones a la partición (teoría de números)
• Principios combinatorios
• tamizado cíclico
• Transformada Z
• Cálculo umbral

Notas

1. Por cierto, también tenemos una fórmula correspondiente cuando m < 0 dada por
   $${\displaystyle \sum _{n=0}^{\infty }g_{n+m}z^{n}={\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}\,.}$$

Referencias

1. Knuth, Donald E. (1997). "§1.2.9 Funciones generadoras". Algoritmos fundamentales . El arte de la programación informática . vol. 1 (3ª ed.). Addison-Wesley. ISBN 0-201-89683-4.
2. Este término alternativo ya se puede encontrar en EN Gilbert (1956), "Enumeration of Labeled Graphs", Canadian Journal of Mathematics 3, p. 405–411, pero su uso es raro antes del año 2000; desde entonces parece estar aumentando.
3. Flajolet y Sedgewick 2009, pág. 95
4. Apostol, Tom M. (1976), Introducción a la teoría analítica de números , Textos de pregrado en matemáticas, Nueva York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, SEÑOR  0434929, Zbl  0335.10001págs.42–43
5. Wilf 1994, pág. 56
6. Wilf 1994, pág. 59
7. Resistente, GH; Wright, EM; Heath-Brown, DR; Silverman, JH (2008). Introducción a la teoría de los números (6ª ed.). Prensa de la Universidad de Oxford. pag. 339.ISBN _ 9780199219858.
8. Spivey, Michael Z. (2007). "Sumas combinatorias y diferencias finitas". Matemáticas discretas . 307 (24): 3130–3146. doi : 10.1016/j.disc.2007.03.052 . SEÑOR  2370116.
9. Mathar, RJ (2012). "Otra tabla más de integrales". arXiv : 1207.5845 [matemáticas.CA].v4 ecuación. (0.4)
10. Graham, Knuth y Patashnik 1994, Tabla 265 en §6.1 para identidades de suma finita que involucran los triángulos numéricos de Stirling.
11. Lando 2003, §2.4
12. Ejemplo de Stanley, Richard P.; Fomín, Sergey (1997). "§6.3". Combinatoria enumerativa: volumen 2. Estudios de Cambridge en Matemáticas Avanzadas. vol. 62. Prensa de la Universidad de Cambridge. ISBN 978-0-521-78987-5.
13. Knuth 1997, §1.2.9
14. Solución a Graham, Knuth y Patashnik 1994, p. 569, ejercicio 7.36
15. Flajolet y Sedgewick 2009, §B.4
16. Schneider, C. (2007). "La suma simbólica ayuda a la combinatoria". Sem. Lotario. Combinar . 56 : 1–36.
17. Para obtener información más completa sobre las propiedades de las fracciones J , consulte:
    • Flajolet, P. (1980). «Aspectos combinatorios de fracciones continuas» (PDF) . Matemáticas discretas . 32 (2): 125-161. doi :10.1016/0012-365X(80)90050-3.
    • Muro, HS (2018) [1948]. Teoría analítica de fracciones continuas. Dover. ISBN 978-0-486-83044-5.
18. Consulte los siguientes artículos:
    • Schmidt, Maxie D. (2016). "Fracciones continuas para funciones generadoras de series cuadradas". arXiv : 1612.02778 [matemáticas.NT].
    • — (2017). "Fracciones continuas tipo Jacobi para las funciones generadoras ordinarias de funciones factoriales generalizadas". Diario de secuencias enteras . 20 . arXiv : 1610.09691 . 17.3.4.
    • — (2017). "Fracciones continuas tipo Jacobi y congruencias para coeficientes binomiales módulo enteros h ≥ 2". arXiv : 1702.01374 [matemáticas.CO].
19. "Identidad de la serie Lambert". Desbordamiento matemático . 2017.
20. Bien, IJ (1986). "Sobre aplicaciones de distribuciones simétricas de Dirichlet y sus mezclas a tablas de contingencia". Anales de Estadística . 4 (6): 1159–1189. doi : 10.1214/aos/1176343649 .
21. Consulte el uso de estos términos en Graham, Knuth y Patashnik 1994, §7.4 sobre funciones generadoras de secuencias especiales.
22. Graham, Knuth y Patashnik 1994, §8.3
23. Graham, Knuth y Patashnik 1994, Ejemplo 6 en §7.3 para conocer otro método y la configuración completa de este problema utilizando funciones generadoras. Este enfoque más "complicado" se presenta en la Sección 7.5 de la misma referencia.
24. Lando 2003, §5
25. Hardy y col. 2008, §19.12
26. Resistente, GH; Wright, EM Introducción a la teoría de números .p.288, Th.361
27. Graham, Knuth y Patashnik 1994, pág. 535, ejercicio 5.71
28. Knuth, DE (1992). "Polinomios de convolución". Matemática J. 2 : 67–78. arXiv : matemáticas/9207221 . Código Bib : 1992 matemáticas ...... 7221K.
29. Véase también las 1031 funciones generadoras que se encuentran en Plouffe, Simon (1992). Approximations de séries génératrices et quelques conjectures [ Aproximaciones de funciones generadoras y algunas conjeturas ] (Maestros) (en francés). Universidad de Québec en Montreal. arXiv : 0911.4975 .

Citas

• Aigner, Martín (2007). Un curso de enumeración. Textos de Posgrado en Matemáticas. vol. 238. Saltador. ISBN 978-3-540-39035-0.
• Doubilet, Pedro; Rota, Gian-Carlo ; Stanley, Richard (1972). "Sobre los fundamentos de la teoría combinatoria. VI. La idea de función generadora". Actas del Sexto Simposio de Berkeley sobre probabilidad y estadística matemática . 2 : 267–318. Zbl  0267.05002.Reimpreso en Rota, Gian-Carlo (1975). "3. La idea de función generadora". Cálculo de operadores finitos . Con la colaboración de P. Doubilet, C. Greene, D. Kahaner, A. Odlyzko y R. Stanley . Prensa académica. págs. 83-134. ISBN 0-12-596650-4. Zbl  0328.05007.
• Flajolet, Philippe ; Sedgewick, Robert (2009). Combinatoria Analítica . Prensa de la Universidad de Cambridge. ISBN 978-0-521-89806-5. Zbl  1165.05001.
• Goulden, Ian P.; Jackson, David M. (2004). Enumeración combinatoria . Publicaciones de Dover . ISBN 978-0486435978.
• Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). "Capítulo 7: Generación de funciones". Matemáticas concretas. Una base para la informática (2ª ed.). Addison-Wesley. págs. 320–380. ISBN 0-201-55802-5. Zbl  0836.00001.
• Lando, Sergei K. (2003). Conferencias sobre funciones generadoras. Sociedad Matemática Estadounidense. ISBN 978-0-8218-3481-7.
• Wilf, Herbert S. (1994). Funcionalidad generadora (2ª ed.). Prensa académica. ISBN 0-12-751956-4. Zbl  0831.05001.

enlaces externos

• "Introducción a las funciones generadoras ordinarias" por Mike Zabrocki, Universidad de York, Matemáticas y Estadística
• "Función generadora", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Funciones generadoras, índices de potencia y cambio de monedas al corte del nudo
• "Funciones generadoras" de Ed Pegg Jr. , Proyecto de demostraciones Wolfram , 2007.