Función generadora

ImprimirCitar

Serie de energía formal; coeficientes codifican información sobre una secuencia indexada por números naturales

En matemáticas, una función generadora es una forma de codificar una secuencia infinita de números ( $a n$ ) tratándolos como los coeficientes de una serie de potencia formal. Esta serie se llama la función generadora de la secuencia. A diferencia de una serie ordinaria, no se requiere que la serie de potencia 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. 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.

Hay varios tipos de funciones generadoras, incluidas funciones generadoras ordinarias, funciones generadoras exponenciales, serie Lambert, serie Bell, y series de Dirichlet; definiciones y ejemplos se dan a continuación. 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 pueden manejarse 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 los detalles del problema que se esté abordando.

Las funciones generadoras a menudo se expresan en forma cerrada (en lugar de como una serie), mediante alguna expresión que involucra 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 se puede interpretar como una función que se puede evaluar en valores concretos (suficientemente pequeños) de $x$ , y que tiene la serie formal como su expansión en serie; esto explica la designación de "funciones generadoras". Sin embargo, no se requiere que tal interpretación sea posible, porque no se requiere que las series formales den una serie convergente cuando se sustituye un valor numérico distinto de cero por $x. Además, no todas las expresiones que son significativas como funciones de x son significativas como expresiones que designan series formales; por ejemplo, las potencias fraccionarias y negativas de x son ejemplos de funciones que no tienen una serie de potencia 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, 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 despreocupadamente, que podrían ser embarazosos, los ponemos a todos en una bolsa, y entonces sólo tenemos 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 mostrar.
—Herbert Wilf, Generación de funciones (1994)

Función generadora ordinaria (OF)

La función generadora ordinaria de una secuencia $a n es$

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

Cuando el término función generadora se usa sin calificación, generalmente se entiende como una función generadora ordinaria.

Si $a n$ 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 arreglos con múltiples índices. Por ejemplo, la función generadora ordinaria de un arreglo 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 $a n es$

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

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

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, tome la secuencia de Fibonacci ${f n}$ que satisface la relación de recurrencia lineal <span class="texhtml" 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 sus derivadas pueden demostrar fácilmente que satisfacen la ecuación diferencial $EF″(x) = EF'(x) + EF (x)$ como un análogo directo con 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 derivado que actúa sobre $x n$ .

Función generadora de Poisson

La función generadora de Poisson de una secuencia $a n 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 Lambert

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 los desarrollos de series de potencias

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

para enteros $n \geq 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 lo contrario, el primer término no estaría definido.

Serie de campanas

La serie de Bell de una secuencia $a n$ es una expresión en términos de tanto una indeterminada $x$ como una prima $p$ y está dada por

{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 estrictamente series de potencia formales. La función generadora de series de Dirichlet de una secuencia $a n$ es

{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 $a n$ es un multiplicativo función, en cuyo caso tiene una expresión de producto de Euler 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 $a n$ es un carácter de Dirichlet, entonces su función generadora de series de Dirichlet es llamada 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 DGF. Es decir, podemos demostrar 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.

Funciones generadoras de secuencias de polinomios

La idea de generar funciones se puede extender a secuencias de otros objetos. Así, por ejemplo, las sucesiones 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 generatrices ordinarias, correspondientes a sucesiones finitas, o sucesiones equivalentes 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 generación ordinaria la función es la serie geométrica

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

El lado izquierdo es la expansión de la serie 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 (es decir, que todos los coeficientes excepto el de $x 0$ son iguales a 0). Además, no puede haber otra serie de potencias con esta propiedad. Por lo tanto, el lado izquierdo designa el inverso multiplicativo de $1 - x$ en el anillo de series de potencias.

Las expresiones para la función generatriz ordinaria de otras secuencias se derivan fácilmente de esta. Por ejemplo, la sustitución $x \to ax$ proporciona la función generadora de la secuencia geométrica $1, a, a 2, a 3,...$ 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 la expansión 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$ , por ejemplo para la secuencia 1, 0, 1, 0, 1, 0, 1, 0,... (que omite $x, x 3, x 5,...$ ) 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 ejecutando la variable $n \to n + 1$ , uno 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 $(n + 2 2)$ , de modo que

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

Más generalmente, para cualquier número 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},}

uno 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 coeficiente binomial:

{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 desarrollar alternativamente para generar esta misma secuencia de cuadrados como una suma de derivadas de la serie geométrica en 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]+xDleft[{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 que para los enteros positivos $m \geq 1$

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

donde ${n k}$ indican los números de Stirling del 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}}},}

para que podamos formar las funciones generadoras análogas sobre las $m$ ésimas potencias integrales 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 que

{displaystyle sum _{n=0}^{infty }n^{m}z^{n}=sum _{j=0}^{m}{begin{Bmatrix}m+1\j+1end{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 razón de dos polinomios de grado finito) si y solo si la secuencia es una secuencia recursiva lineal con coeficientes constantes; esto generaliza los ejemplos anteriores. A la inversa, 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 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 sucesiones 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 a través de 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 cuasi-polinómicas de la forma

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

donde las raíces recíprocas, $ρ i \in ℂ$ , son escalares fijos y donde $p i (n)$ es un polinomio en $n$ para todos $1 \leq i \leq l$ .

En general, los productos de Hadamard de funciones racionales producen funciones generadoras racionales. Del mismo modo, si

{displaystyle F(s,t):=sum _{m,ngeq 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

{displaystyle F(s,t):=sum _{i,jgeq 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 generatrices ordinarias produce una convolución discreta (el producto de Cauchy) de las secuencias. Por ejemplo, la secuencia de sumas acumuladas (en comparación con la fórmula de Euler-Maclaurin un poco más general)

{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 los números enteros $m \geq 1$ , tenemos las siguientes dos identidades análogas para las funciones generadoras modificadas que enumeran las variantes de secuencia desplazada 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 en serie 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]zcdot 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 $k$ ésimo factorial descendente:

{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 }}kin mathbb {N}.}

Usando los números de Stirling del segundo tipo, que se puede convertir en otra fórmula para multiplicarse por $n^{k}$ como sigue (ver el artículo principal sobre la generación de transformaciones de funciones):

{displaystyle sum _{j=0}^{k}{begin{Bmatrix}k\jend{Bmatrix}}z^{j}F^{(j)}(z)=sum _{n=0}^{infty }n^{k}f_{n}z^{n}quad {text{for all }}kin 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 de la serie zeta y sus generalizaciones se definen como una transformación basada en derivadas de funciones generadoras, o alternativamente en términos y realizando una transformación integral en la función generadora de secuencias. Aquí se analizan las operaciones relacionadas con la realización de la integración fraccionaria en una función generadora de secuencias.

Enumeración de progresiones aritméticas de sucesiones

En esta sección damos fórmulas para generar funciones enumerando la secuencia ${f an + b}$ dada una función generadora ordinaria $F (z)$ , donde $a \geq 2$ , $0 \leq b < a$ y $a$ y $b$ son números enteros (consulte el artículo principal sobre transformaciones). Para $a = 2$ , esto es simplemente la descomposición familiar 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}}}

Más generalmente, suponga que $a \geq 3$ y que $ω a = exp 2 πi / a$ denota el $una$ ésima raíz primitiva de la unidad. Entonces, como aplicación de la transformada discreta de Fourier, tenemos la fórmula

{displaystyle sum _{n=0}^{infty }f_{an+b}z^{an+b}={frac {1}{a}}sum _{m=0}^{a-1}omega _{a}^{-mb}Fleft(omega _{a}^{m}zright).}

Para números enteros $m \geq 1$ , otra fórmula útil proporciona progresiones aritméticas algo invertidas, repitiendo efectivamente cada coeficiente $m$ veces — son generados por la identidad

{displaystyle sum _{n=0}^{infty }f_{leftlfloor {frac {n}{m}}rightrfloor }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

Se dice que una serie de potencias formal (o función) $F (z)$ es holonómica si satisface una ecuación diferencial lineal de la forma

{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 racional funciones, $ℂ(z)$ . De manera equivalente, $F (z)$ es holonómico si el espacio vectorial sobre $ℂ(z)$ generado por el conjunto de todas sus derivadas es de dimensión finita.

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 lo 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 $n \geq n 0$ suficientemente grandes y donde $ĉ 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 equivalente. Las funciones holonómicas se cierran bajo la operación del producto Hadamard $⊙$ al generar funciones.

Ejemplos

Las funciones $e z$ , $log z$ , $cos z$ , $arcosen z$ , $\sqrt 1 + z$ , la función de dilogaritmo $Li 2 (z)$ , las funciones hipergeométricas generalizadas $p F q (...;...; z)$ y las funciones definidas por la serie de potencias

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

y lo no convergente

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

son todos holonómicos.

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

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

Las herramientas para procesar y trabajar con $P$ -secuencias 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 Guess para adivinar $P$ -recurrencias para secuencias de entrada arbitrarias (útil para matemáticas experimentales y exploración) y el paquete Sigma que es capaz de encontrar recurrencias P para muchas sumas y resolver soluciones de forma cerrada para recurrencias $P$ que involucran números armónicos generalizados. Otros paquetes enumerados en este sitio RISC en particular están destinados a trabajar específicamente con funciones de generación holonómicas.

Relación con la transformada de Fourier en tiempo discreto

Cuando la serie converge absolutamente,

{displaystyle Gleft(a_{n};e^{-iomega }right)=sum _{n=0}^{infty }a_{n}e^{-iomega n}}

a 0, a 1,...

Crecimiento asintótico de una secuencia

En cálculo, a menudo se puede usar la tasa de crecimiento de los coeficientes de una serie de potencias para deducir un radio de convergencia de la serie de potencias. El reverso también puede sostenerse; 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 (a n; x)$ que tiene un radio finito de convergencia 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 uno de $A (x)$ y $B (x)$ es una función que es analítica para un radio de convergencia mayor que $r$ (o está completo), y donde $B (r) \neq 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},,}

A menudo, este enfoque se puede repetir para generar varios términos en una serie asintótica para $a n . En particular,$

{displaystyle Gleft(a_{n}-{frac {B(r)}{r^{alpha }}}{binom {n+beta -1}{n}}left({frac {1}{r}}right)^{n};xright)=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 se puede buscar mediante el hallazgo de $A$ , B, $α$ , $β$ y $r$ para describir la generación función, como arriba.

Es posible un análisis asintótico similar para las funciones generadoras exponenciales; con una función generadora exponencial, es $a n / n!$ que crece de acuerdo con 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 sucesión de cuadrados

Como se dedujo 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 comprobar 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 los números catalanes

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 arreglos con varios índices. Estas se denominan funciones generadoras multivariadas o, a veces, funciones supergeneradoras. Para dos variables, a menudo se denominan funciones generadoras bivariadas.

Por ejemplo, dado que $(1 + x) n$ es la generación ordinaria función para coeficientes binomiales para un $n$ fijo, se puede solicitar una función generadora bivariada que genere los coeficientes binomiales $(n k)$ para todos los $k$ y $n$ . Para hacer esto, considere $(1 + x) n$ como una secuencia en $n$ , y busque la función generadora en $y$ que tiene estos valores de secuencia como coeficientes. Dado que la función generadora para $a n$ 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

Expansiones de fracciones continuas (formales) tipo Jacobi y tipo Stieltjes ( $J$ -fracciones y $S$ -fracciones, respectivamente) cuyos $h$ ésimos convergentes racionales representan series de potencias precisas de orden 2h son otra forma de expresar las funciones generatrices ordinarias típicamente divergentes para muchas secuencias especiales de una y dos variantes. La forma particular de las fracciones continuas de tipo Jacobi ( $J$ -fractions) se expanden como en la siguiente ecuación y tienen la siguiente correspondiente expansiones de series de potencia con respecto a $z$ para algunas secuencias de componentes específicas que dependen de la aplicación, ${ab i}$ y ${c i}$ , donde $z \neq 0$ denota la variable formal en la segunda expansión de la serie de potencias que se muestra a continuación:

{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 $z^n$ , denotado en breve por $j n ≔ z n] J [viejo] () z)$ , en las ecuaciones anteriores corresponden a soluciones de matriz de las ecuaciones

{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 0 \equiv k 0,0 = 1$ , $j n = k 0, n$ para $n \geq 1$ , $k <sub r, s = 0$ si $r > s$ , y donde para todos los enteros $p, q \geq 0$ , tenemos una relación fórmula de adició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 \geq 0$ (aunque en la práctica cuando $h \geq 2$ ), podemos definir los racionales $h$ th convergentes al infinito $J$ -fracción, $J [\infty] (z)$ , ampliado 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}}

por componente a través de las secuencias, $P h (z)$ y $Q h (z)$ , definido 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 \geq 2$ implica ecuaciones en diferencias finitas adicionales y propiedades de congruencia satisfechas por la secuencia de $j n$ , y para $M h ≔ ab 2 \dots 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 no simbólicas de las secuencias de parámetros ${ab i}$ y ${c i}$ cuando $h \geq 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 de componentes encontradas computacionalmente (y posteriormente comprobadas como correctas en las referencias citadas) en varios casos especiales de las secuencias prescritas, $j n$ , generadas por las expansiones generales de $J$ -fracciones definidas en la primera subsección. Aquí definimos $0 < | a |, | b |, | q | < 1$ y los parámetros $R$ , $α \in ℤ +$ y $x$ serán indeterminados con respecto a estas expansiones, donde el prescrito Las secuencias enumeradas por las expansiones de estas fracciones $J$ se definen en términos del símbolo q-Pochhammer, el símbolo de Pochhammer y el binomio coeficientes

${displaystyle j_{n}}$	$c_{1}$	${displaystyle c_{i}(igeq 2)}$	${displaystyle mathrm {ab} _{i}(igeq 2)}$
${displaystyle q^{n^{2}}}$	$q$	${displaystyle q^{2h-3}left(q^{2h}+q^{2h-2}-1right)}$	${displaystyle q^{6h-10}left(q^{2h-2}-1right)}$
${displaystyle (a;q)_{n}}$	$1-a$	${displaystyle q^{h-1}-aq^{h-2}left(q^{h}+q^{h-1}-1right)}$	${displaystyle aq^{2h-4}left(aq^{h-2}-1right)left(q^{h-1}-1right)}$
${displaystyle left(zq^{-n};qright)_{n}}$	${displaystyle {frac {q-z}{q}}}$	${displaystyle {frac {q^{h}-z-qz+q^{h}z}{q^{2h-1}}}}$	${displaystyle {frac {left(q^{h-1}-1right)left(q^{h-1}-zright)cdot z}{q^{4h-5}}}}$
${displaystyle {frac {(a;q)_{n}}{(b;q)_{n}}}}$	${displaystyle {frac {1-a}{1-b}}}$	${displaystyle {frac {q^{i-2}left(q+abq^{2i-3}+a(1-q^{i-1}-q^{i})+b(q^{i}-q-1)right)}{left(1-bq^{2i-4}right)left(1-bq^{2i-2}right)}}}$	${displaystyle {frac {q^{2i-4}left(1-bq^{i-3}right)left(1-aq^{i-2}right)left(a-bq^{i-2}right)left(1-q^{i-1}right)}{left(1-bq^{2i-5}right)left(1-bq^{2i-4}right)^{2}left(1-bq^{2i-3}right)}}}$
${displaystyle alpha ^{n}cdot left({frac {R}{alpha }}right)_{n}}$	$R$	${displaystyle R+2alpha (i-1)}$	${displaystyle (i-1)alpha {bigl (}R+(i-2)alpha {bigr)}}$
${displaystyle (-1)^{n}{binom {x}{n}}}$	$-x$	${displaystyle -{frac {(x+2(i-1)^{2})}{(2i-1)(2i-3)}}}$	${displaystyle {begin{cases}-{dfrac {(x-i+2)(x+i-1)}{4cdot (2i-3)^{2}}}&{text{for }}igeq 3;\[4px]-{frac {1}{2}}x(x+1)&{text{for }}i=2.end{cases}}}$
${displaystyle (-1)^{n}{binom {x+n}{n}}}$	${displaystyle -(x+1)}$	${displaystyle {frac {{bigl (}x-2i(i-2)-1{bigr)}}{(2i-1)(2i-3)}}}$	${displaystyle {begin{cases}-{dfrac {(x-i+2)(x+i-1)}{4cdot (2i-3)^{2}}}&{text{for }}igeq 3;\[4px]-{frac {1}{2}}x(x+1)&{text{for }}i=2.end{cases}}}$

Los radios de convergencia de estas series correspondientes a la definición de las $J$ -fracciones de tipo Jacobi dadas anteriormente son en general diferente de la de las correspondientes expansiones en serie de potencias que definen las funciones generatrices ordinarias de estas secuencias.

Ejemplos

Generación de funciones para la secuencia de números cuadrados $a n = n 2$ 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 Lambert

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

{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 de caso especial para la función generadora de la función divisoria, $d (n) \equiv σ 0 (n)$ , dado 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 de campanas

{displaystyle operatorname {BG} _{p}left(n^{2};xright)=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};sright)=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 _{2leq aleq n}x^{a}+{binom {m}{2}}{underset {ableq n}{sum _{a=2}^{infty }sum _{b=2}^{infty }}}x^{ab}+{binom {m}{3}}{underset {abcleq n}{sum _{a=2}^{infty }sum _{c=2}^{infty }sum _{b=2}^{infty }}}x^{abc}+{binom {m}{4}}{underset {abcdleq 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 enteros no negativos con totales de fila y columna especificados. Suponga que la tabla tiene $r$ filas y $c$ columnas; las sumas de las filas son $t 1, t 2 ... t r$ y las sumas de las columnas son $s 1, s 2 ... s c$ . Entonces, según I. J. Good, el número de tales tablas es el coeficiente de

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

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

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

{displaystyle G(w,z):=sum _{m,ngeq 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:

{displaystyle {begin{aligned}e^{z+wz}&=sum _{m,ngeq 0}{binom {n}{m}}w^{m}{frac {z^{n}}{n!}}\[4px]e^{w(e^{z}-1)}&=sum _{m,ngeq 0}{begin{Bmatrix}n\mend{Bmatrix}}w^{m}{frac {z^{n}}{n!}}\[4px]{frac {1}{(1-z)^{w}}}&=sum _{m,ngeq 0}{begin{bmatrix}n\mend{bmatrix}}w^{m}{frac {z^{n}}{n!}}\[4px]{frac {1-w}{e^{(w-1)z}-w}}&=sum _{m,ngeq 0}leftlangle {begin{matrix}n\mend{matrix}}rightrangle w^{m}{frac {z^{n}}{n!}}\[4px]{frac {e^{w}-e^{z}}{we^{z}-ze^{w}}}&=sum _{m,ngeq 0}leftlangle {begin{matrix}m+n+1\mend{matrix}}rightrangle {frac {w^{m}z^{n}}{(m+n+1)!}}.end{aligned}}}

Aplicaciones

Varias técnicas: evaluar sumas y abordar 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 = \sum n k = 0 a k$ . Entonces sabemos que $S (z) = A (z) / 1 - z$ para las correspondientes funciones generadoras ordinarias.

Por ejemplo, podemos manipular

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

H k = 1 + 1 / 2 + \dots + 1 / k

{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}},.}

Uso

{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 la transformada binomial

Como otro ejemplo del uso de funciones generadoras para relacionar secuencias y manipular sumas, para una secuencia arbitraria $⟨ f n ⟩$ definimos las dos sucesiones 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 \geq 0

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

{displaystyle S(z)={frac {1}{1-3z}}Fleft({frac {z}{1-3z}}right).}

Dado que la función generadora de la secuencia $⟨ (n + 1)(n + 2)(n + 3) f n ⟩$ viene dado por

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

{displaystyle {tilde {S}}(z)={frac {6}{(1-3z)}}Fleft({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 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) 3

b () z) = 18(1 - 3 z) 3

c () z) = 9(1 - 3 z) 3

d () z) = (1 - 3 z) 3

(1 - 3 z) 3 1 - 9 z + 27 z 2 27 - 27 z 3

Finalmente, se sigue 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: Generación de 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 (consulte también la Sección 7.1 de la misma referencia para obtener imágenes bonitas de series de funciones generadoras). En particular, suponga que buscamos el número total de formas (denotadas $U n$ ) para teselar un mosaico de 3 por $n$ rectángulo con piezas de dominó de 2 por 1 sin marcar. Deje que la secuencia auxiliar, $U n$ , se defina como el número de formas de cubrir un 3 por $n$ sección del rectángulo menos la esquina del rectángulo completo. Buscamos usar estas definiciones para dar una fórmula de forma cerrada para $U n$ sin desglosar más esta definición para manejar la casos de dominó vertical versus horizontal. Observe que las funciones generatrices 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 mutuamente recursivas, para nuestras dos secuencias cuando $n \geq 2$ definido como arriba donde $U 0 = 1$ , $U 1 = 0$ , $V 0 = 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}}}

Dado que tenemos que para todos los enteros $m \geq 0$ , las funciones generadoras de índice desplazado satisfacen

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

Por lo tanto, al realizar simplificaciones algebraicas a la secuencia resultante de las segundas fracciones parciales de la función generadora en la ecuación anterior, encontramos que $U 2 n + 1 \equiv 0$ y eso

{displaystyle U_{2n}=leftlceil {frac {left(2+{sqrt {3}}right)^{n}}{3-{sqrt {3}}}}rightrceil ,,}

n \geq 0

Convolución (productos de 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).

Considerar $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}}}$
Considerar $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}}$
Considere la secuencia triplicada 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}}$
Considerar el $m$ - convolución múltiple de una secuencia con sí misma para algún entero positivo $m \geq 1$ (ver el ejemplo a continuación para una solicitud) ${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 mostrar que para dos variables aleatorias cualesquiera

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

X

Y

n \geq 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}}},}

n

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

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

Un ejemplo donde las convoluciones de funciones generadoras son útiles nos permite resolver una función específica de forma cerrada 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 0 \cdot x 1 \cdot\dots\cdot x n$ para que el orden de multiplicación esté completamente especificado. Por ejemplo, $C 2 = 2$ que corresponde a las dos expresiones $x 0 \cdot (x 1 \cdot x 2)$ y $(x 0 \cdot x 1) \cdot x 2$ . De ello se deduce que la sucesión 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 ngeq 0,,}

C () z)

{displaystyle C(z)=zcdot C(z)^{2}+1,.}

Dado que $C (0) = 1 \neq \infty$ , 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 define implícitamente $C (z)$ anterior implica que

{displaystyle C(z)={frac {1}{1-zcdot C(z)}},,}

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

A fan del orden $n$ se define como un gráfico en los vértices $1,... n}$ con $2 n - 1$ bordes conectados según las siguientes reglas: Vertex 0 está conectado por un solo borde a cada uno del otro $n$ vértices, y vértice $k$ está conectado por un solo borde al siguiente vértice $k + 1$ para todos $1 \leq k . n$ . Hay un fan del orden uno, tres fans del orden dos, ocho fans del orden tres, y así sucesivamente. Un árbol de azotes es un subgrafo de un gráfico que contiene todos los vértices originales y que contiene suficientes bordes para hacer este subgrafo conectado, pero no tantos bordes que hay un ciclo en el subgrafo. Preguntamos cuántos árboles azotados $f n$ de un fan del orden $n$ son posibles para cada $n \geq 1$ .

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 = 4 + 3 \cdot 1 + 2 \cdot 2 + 1 \cdot 3 + 2 \cdot 1 \cdot 1 + 1 \cdot 2 \cdot 1 + 1 \cdot 1 \cdot 2 + 1 \cdot 1 \cdot 1 \cdot 1 = 21$ , que es una suma sobre las circunvoluciones $m$ -fold de la secuencia $g n = n = [z n] z / (1 - z) 2$ para $m ≔ 1, 2, 3, 4$ . Más generalmente, podemos escribir una fórmula para esta sucesión como

0}sum _{scriptstyle k_{1}+k_{2}+cdots +k_{m}=n atop scriptstyle k_{1},k_{2},ldotsk_{m}>0}g_{k_{1}}g_{k_{2}}cdots g_{k_{m}},,}" display="block" xmlns="http://www.w3.org/1998/Math/MathML">fn=.. m■0.. k1+k2+⋯ ⋯ +km=nk1,k2,...... ,km■0gk1gk2⋯ ⋯ gkm,{displaystyle F_{n}=sum - ¿Qué? _{scriptstyle k_{1}+k_{2}+cdots ## k_{2},ldotsk_{m}=n atop scriptstyle k_{1},k_{2},ldotsk_{m}]}g_{k_{2}cdots G_{k_{m},}0}sum _{scriptstyle k_{1}+k_{2}+cdots +k_{m}=n atop scriptstyle k_{1},k_{2},ldotsk_{m}>0}g_{k_{1}}g_{k_{2}}cdots g_{k_{m}},,}" aria-hidden="true" class="mwe-math-fallback-image-display" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de20fae658d8e3fc868770290d81ce4a726fb01f" style="vertical-align: -5.338ex; width:38.049ex; height:7.843ex;"/>

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

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

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

A veces, la suma $s n$ es complicada y no siempre es fácil de evaluar. El "Parámetro libre" El método 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 suma. Cuando n no aparece explícitamente en la sumatoria, podemos considerar $n$ como un parámetro “libre” y tratar $s n$ como un coeficiente de $F (z) = \sum s n z n$ , cambia el orden de las sumatorias en $n$ y $k$ , y tratar de 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,nin 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 sumatoria 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 es $z 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 }}mgeq 1,,\{}[n=0]&{text{for }}m=0,.end{cases}}}

Es instructivo usar el mismo método nuevamente 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},.}

Al intercambiar la sumatoria (y el #34;aceite de serpiente ") se obtiene

{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 \geq 1

Las funciones generadoras prueban congruencias

Decimos que dos funciones generadoras (serie de potencias) son congruentes módulo $m$ , escrito $A (z) \equiv B (z) (modificación m)$ si sus coeficientes son congruentes módulo $m$ para todo $n \geq 0$ , es decir, $a n \equiv b n (mod m)$ para todos los casos relevantes de los enteros $n$ (tenga en cuenta que No es necesario suponer que $m$ es un número entero aquí; es muy posible que tenga un valor polinomial en algún $x$ , por ejemplo). Si el "más simple" la función generadora del lado derecho, $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 valores enteros $m \geq 2$ . Por ejemplo, podemos probar 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}},,}

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

Uno de los métodos más útiles, si no francamente poderosos, para obtener congruencias para secuencias enumeradas por funciones generadoras especiales módulo cualquier número entero (es decir, no solo potencias primas $p k$ ) se proporciona en la sección sobre representaciones de fracciones continuas de funciones generadoras ordinarias (incluso no convergentes) por $J$ -fracciones anteriores. 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 Lectures on Generating Functions de Lando de la siguiente manera:

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

{displaystyle A(z)={frac {1}{1-c_{1}z}}{frac {p_{1}z^{2}}{1-c_{2}z}}{frac {p_{2}z^{2}}{1-c_{3}z}}cdots}

y eso

A p () z)

denota los

p

t convergent to this continued fraction expansion defined such that

a n = z n] A p () z)

para todos

0 \leq n 2 p

. Entonces:

la función $A p () z)$ es racional para todos $p \geq 2$ donde asumimos que uno de los criterios de divisibilidad $p Silencio p 1, p 1 p 2, p 1 p 2 p 3$ es conocido, es decir, $p Silencio p 1 p 2 \dots p k$ para algunos $k \geq 1$ ; y
si el entero $p$ divide el producto $p 1 p 2 \dots p k$ , entonces tenemos $A () z) A k () z (modelo) 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 enteras.

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\kend{bmatrix}}x^{k}=x(x+1)(x+2)cdots (x+n-1),,quad ngeq 1,,}

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

{displaystyle S_{n}(x)=[x(x+1)]cdot [x(x+1)]cdots =x^{leftlceil {frac {n}{2}}rightrceil }(x+1)^{leftlfloor {frac {n}{2}}rightrfloor },,}

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

{displaystyle {begin{bmatrix}n\kend{bmatrix}}equiv {binom {leftlfloor {frac {n}{2}}rightrfloor }{k-leftlceil {frac {n}{2}}rightrceil }}{pmod {2}},,}

y, en consecuencia, muestra que $[n k]$ es par siempre que $k < ⌊ n / 2 ⌋$ .

Del mismo modo, podemos reducir los productos del lado derecho que definen las funciones generadoras de números de Stirling módulo 3 para obtener expresiones un poco más complicadas siempre que

{displaystyle {begin{aligned}{begin{bmatrix}n\mend{bmatrix}}&equiv [x^{m}]left(x^{leftlceil {frac {n}{3}}rightrceil }(x+1)^{leftlceil {frac {n-1}{3}}rightrceil }(x+2)^{leftlfloor {frac {n}{3}}rightrfloor }right)&&{pmod {3}}\&equiv sum _{k=0}^{m}{begin{pmatrix}leftlceil {frac {n-1}{3}}rightrceil \kend{pmatrix}}{begin{pmatrix}leftlfloor {frac {n}{3}}rightrfloor \m-k-leftlceil {frac {n}{3}}rightrceil end{pmatrix}}times 2^{leftlceil {frac {n}{3}}rightrceil +leftlfloor {frac {n}{3}}rightrfloor -(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 serie 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)$ es generada por el recíproco infinito q-producto de símbolo de Pochhammer (o $z$ -producto de Pochhammer según sea el caso) dado por

{displaystyle {begin{aligned}sum _{n=0}^{infty }p(n)z^{n}&={frac {1}{left(1-zright)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 notablemente los siguientes resultados, aunque todavía hay muchas preguntas abiertas sobre las formas de las congruencias de enteros relacionadas para la función:

{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 usar funciones generatrices y manipulaciones de congruencias para series de potencias formales para dar una prueba muy elemental de la primera de estas congruencias mencionadas anteriormente.

Primero, observamos que en la función generadora del coeficiente binomial

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

1, z 5, z 10,...

{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 zcdot {frac {left(1-z^{5}right)left(1-z^{10}right)cdots }{left(1-zright)left(1-z^{2}right)cdots }}=zcdot 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-zright)left(1-z^{2}right)cdots right)^{5}}},,}

z 5 m + 5

z \cdot ((1 - z)(1 - z 2)\dots) 4

m

{displaystyle {begin{aligned}sum _{n=1}^{infty }p(n-1)z^{n}&={frac {z}{(1-z)left(1-z^{2}right)cdots }}\[6px]&=zcdot {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) \equiv 0 (mod 5)

m \geq 0

Transformaciones de funciones generadoras

Hay una serie de transformaciones de funciones generadoras que proporcionan otras aplicaciones (ver 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 forma de $S (z) = g (z) A (f (z))$ que involucra la función de generación de secuencia original. Por ejemplo, si las sumas son

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

{displaystyle S(z)={frac {z^{m}}{(1-z)^{m+1}}}Aleft({frac {z}{(1-z)^{2}}}right)}

También hay fórmulas integrales para convertir entre el OGF de una secuencia, $F (z)$ , 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}{2pi }}int _{-pi }^{pi }Fleft(ze^{-ivartheta }right)e^{e^{ivartheta }},dvartheta ,,end{aligned}}}

siempre que estas integrales converjan para los valores apropiados de $z$ .

Otras aplicaciones

Las funciones generadoras se utilizan para:

Encuentra 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.
Encontrar relaciones entre secuencias - si las funciones generadoras de dos secuencias tienen una forma similar, entonces las secuencias mismas pueden estar relacionadas.
Explore el comportamiento asintotico de las secuencias.
Probar identidades que implican secuencias.
Resolver problemas de enumeración en combinatoria y encodificar sus soluciones. Los polinomios Rook son un ejemplo de una aplicación en combinatoria.
Evaluar sumas infinitas.

Otras funciones generadoras

Ejemplos

Los ejemplos de secuencias polinómicas generadas por funciones generadoras más complejas incluyen:

Apell polinomials
Polinomios Chebyshev
Difference polynomials
Polinomios Appell generalizados
q-difference polinomials

Otras secuencias generadas por funciones generadoras más complejas:

Doble funciones de generación exponencial. Por ejemplo: Array de Aitken: Triángulo de Números
Hadamard productos de funciones generadoras y funciones generadoras diagonales, y sus correspondientes transformaciones integrales

Polinomios de convolución

El artículo de Knuth titulado "Convolution Polynomios" define una clase generalizada de secuencias polinomiales de convolución por sus funciones generadoras especiales de la forma

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

F

F (0) = 1

Decimos que una familia de polinomios, $f 0, f 1, f 2,\dots$ , forma una familia de convolución si $grado f n \leq n$ y si la siguiente condición de convolución se cumple para todos los $x$ , $y$ y para todos $n \geq 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 cero no idénticas, esta definición es equivalente a requerir que la secuencia tenga una función generadora ordinaria de la primera forma dada arriba.

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

La secuencia $n \cdot f n () x)$ es de tipo binomio
Los valores especiales de la secuencia incluyen $f n 1) z n] F () z)$ y $f n (0) δ n,0$ , y
Para arbitrarios (fijados) $x, Sí., t C$ , estos polinomios satisfacen las fórmulas de la forma convolutiva

{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 $t \in ℂ$ , hemos modificado funciones generadoras para estas secuencias polinómicas de convolución dadas por

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

F t () z)

F t () z) F () x F t () z) t)

. f n () x .

. g n () x .

F () z) x

G () z) x

t

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

Ejemplos de secuencias de polinomios de convolución incluyen la serie de potencia binomial, $𝓑 t (z) = 1 + z 𝓑 t (z) t$ , denominados polinomios de árbol, los números de Bell, $B (n)$ , los polinomios de Laguerre y los polinomios de convolución de Stirling.

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 Matemáticas concretas y en la Sección 2.5 de Funcionología de generación de Wilf se encuentran varias funciones útiles y especiales de generación de secuencias. Otras funciones especiales de generación de nota incluyen las entradas en la siguiente tabla, que de ninguna manera está completa.

Serie de energía formal	Fórmula de creación de funciones	Notas
${displaystyle sum _{n=0}^{infty }{binom {m+n}{n}}left(H_{n+m}-H_{m}right)z^{n}}$	${displaystyle {frac {1}{(1-z)^{m+1}}}ln {frac {1}{1-z}}}$	$H_{n}$ es un número armónico de primer orden
${displaystyle sum _{n=0}^{infty }B_{n}{frac {z^{n}}{n!}}}$	${displaystyle {frac {z}{e^{z}-1}}}$	$B_{n}$ es un número de Bernoulli
${displaystyle sum _{n=0}^{infty }F_{mn}z^{n}}$	${displaystyle {frac {F_{m}z}{1-(F_{m-1}+F_{m+1})z+(-1)^{m}z^{2}}}}$	$F_{n}$ es un número de Fibonacci y ${displaystyle min mathbb {Z} ^{+}}$
${displaystyle sum _{n=0}^{infty }left{{begin{matrix}n\mend{matrix}}right}z^{n}}$	${displaystyle (z^{-1})^{overline {-m}}={frac {z^{m}}{(1-z)(1-2z)cdots (1-mz)}}}$	$x^{overline{n}}$ denota el creciente factorial, o el símbolo Pochhammer y algunos enteros $mgeq 0$
${displaystyle sum _{n=0}^{infty }left[{begin{matrix}n\mend{matrix}}right]z^{n}}$	${displaystyle z^{overline {m}}=z(z+1)cdots (z+m-1)}$
${displaystyle sum _{n=1}^{infty }{frac {(-1)^{n-1}4^{n}(4^{n}-2)B_{2n}z^{2n}}{(2n)cdot (2n)!}}}$	${displaystyle ln {frac {tan(z)}{z}}}$
${displaystyle sum _{n=0}^{infty }{frac {(1/2)^{overline {n}}z^{2n}}{(2n+1)cdot n!}}}$	${displaystyle z^{-1}arcsin(z)}$
${displaystyle sum _{n=0}^{infty }H_{n}^{(s)}z^{n}}$	${displaystyle {frac {operatorname {Li} _{s}(z)}{1-z}}}$	$operatorname {Li} _{s}(z)$ es la función de polilogaritmo y ${displaystyle H_{n}^{(s)}}$ es un número armónico generalizado $1}" xmlns="http://www.w3.org/1998/Math/MathML">R R ()s)■1{displaystyle Re (s)}1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9ea5968732ea35f67b36093364400e0fd8ca23bf" style="vertical-align: -0.838ex; width:9.085ex; height:2.843ex;"/>$
${displaystyle sum _{n=0}^{infty }n^{m}z^{n}}$	${displaystyle sum _{0leq jleq m}left{{begin{matrix}m\jend{matrix}}right}{frac {j!cdot z^{j}}{(1-z)^{j+1}}}}$	${displaystyle left{{begin{matrix}n\mend{matrix}}right}}$ es un número impresionante del segundo tipo y donde los términos individuales en la expansión satisfacen ${displaystyle {frac {z^{i}}{(1-z)^{i+1}}}=sum _{k=0}^{i}{binom {i}{k}}{frac {(-1)^{k-i}}{(1-z)^{k+1}}}}$
$<math alttext="{displaystyle sum _{k.. k.n()n− − kk)nn− − kzk{displaystyle sum _{k maden}{binom {n-k}{}{frac} {n} {n-k}z^{k}<img alt="{displaystyle sum _{k$	${displaystyle left({frac {1+{sqrt {1+4z}}}{2}}right)^{n}+left({frac {1-{sqrt {1+4z}}}{2}}right)^{n}}$
${displaystyle sum _{n_{1},ldotsn_{m}geq 0}min(n_{1},ldotsn_{m})z_{1}^{n_{1}}cdots z_{m}^{n_{m}}}$	${displaystyle {frac {z_{1}cdots z_{m}}{(1-z_{1})cdots (1-z_{m})(1-z_{1}cdots z_{m})}}}$	El caso dos variables es dado por ${displaystyle M(w,z):=sum _{m,ngeq 0}min(m,n)w^{m}z^{n}={frac {wz}{(1-w)(1-z)(1-wz)}}}$
${displaystyle sum _{n=0}^{infty }{binom {s}{n}}z^{n}}$	${displaystyle (1+z)^{s}}$	${displaystyle sin mathbb {C} }$
${displaystyle sum _{n=0}^{infty }{binom {n}{k}}z^{n}}$	${displaystyle {frac {z^{k}}{(1-z)^{k+1}}}}$	$kin mathbb {N}$
${displaystyle sum _{n=1}^{infty }log {(n)}z^{n}}$	${displaystyle left.-{frac {partial }{partial s}}operatorname {{Li}_{s}(z)} right\|_{s=0}}$

Historia

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

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

Contenido relacionado

Más resultados...

Función generadora

Definiciones

Función generadora ordinaria (OF)

Función generadora exponencial (EGF)

Función generadora de Poisson

Serie Lambert

Serie de campanas

Funciones generadoras de series de Dirichlet (DGF)

Funciones generadoras de secuencias de polinomios

Funciones generadoras ordinarias

Ejemplos de generación de funciones para secuencias simples

Funciones racionales

Operaciones sobre funciones generadoras

La multiplicación produce convolución

Índices de secuencia cambiante

Diferenciación e integración de funciones generadoras

Enumeración de progresiones aritméticas de sucesiones

P-secuencias recursivas y funciones generadoras holonómicas

Definiciones

Ejemplos

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

Relación con la transformada de Fourier en tiempo discreto

Crecimiento asintótico de una secuencia

Crecimiento asintótico de la sucesión de cuadrados

Crecimiento asintótico de los números catalanes

Funciones generadoras bivariadas y multivariadas

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

Definiciones

Propiedades de las h-ésimas funciones convergentes

Ejemplos

Ejemplos

Función generadora ordinaria

Función generadora exponencial

Serie Lambert

Serie de campanas

Función generadora de series de Dirichlet

Funciones generadoras multivariadas

Aplicaciones

Varias técnicas: evaluar sumas y abordar otros problemas con funciones generadoras

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

Ejemplo 2: sumas de coeficientes binomiales modificados y la transformada binomial

Ejemplo 3: Generación de funciones para secuencias mutuamente recursivas

Convolución (productos de Cauchy)

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

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

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

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

Las funciones generadoras prueban congruencias

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

Congruencias para la función de partición

Transformaciones de funciones generadoras

Otras aplicaciones

Otras funciones generadoras

Ejemplos

Polinomios de convolución

Tablas de funciones generadoras especiales

Historia

Contenido relacionado

Pseudoprima de Fermat

Subconjunto

Curtosis