Función generadora

Series 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 . Las funciones generadoras suelen expresarse en forma cerrada (en lugar de como una serie), mediante alguna expresión que implica operaciones sobre la serie formal.

Existen varios tipos de funciones generadoras, entre ellas las funciones generadoras ordinarias , las funciones generadoras exponenciales , las series de Lambert , las series de Bell y las series de Dirichlet . 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 variar considerablemente. La función generadora particular, si la hay, que sea más útil en un contexto determinado dependerá de la naturaleza de la secuencia y de los detalles del problema que se aborde.

Las funciones generadoras a veces se denominan series generadoras , ^[1] ya que se puede decir que una serie de términos es el generador de su secuencia de coeficientes de términos.

Historia

Las funciones generadoras fueron introducidas por primera vez por Abraham de Moivre en 1730, para resolver el problema general de recurrencia lineal. ^[2]

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 las funciones generadoras mucho antes que Laplace [...]. Aplicó esta herramienta matemática a varios problemas del análisis combinatorio y la teoría de números .

Definición

Una función generadora es un dispositivo similar a una bolsa. En lugar de llevar muchos objetos pequeños de forma separada, lo que podría resultar embarazoso, los colocamos todos en una bolsa y, de ese modo, solo 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 mostrarlos.

—  Herbert Wilf , Función generadora (1994)

Convergencia

A diferencia de una serie ordinaria, no se requiere que la serie de potencias formales converja : de hecho, la función generadora no se considera realmente una función , y la "variable" sigue siendo una indeterminada . Se puede generalizar a series de potencias formales en más de una indeterminada, para codificar información sobre matrices multidimensionales infinitas de números. Por lo tanto, las funciones generadoras no son funciones en el sentido formal de una aplicación de un dominio a un codominio .

Estas expresiones en términos de la indeterminada  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 en 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 dicha 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 .

Limitaciones

No todas las expresiones que tienen significado como funciones de  x tienen significado 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 formales correspondiente.

Tipos

Función generadora ordinaria (OGF)

Cuando se utiliza el término función generadora sin calificación, generalmente se entiende que significa una función generadora ordinaria. La función generadora ordinaria de una secuencia a _n es: Si a _n es la función de masa de probabilidad de una variable aleatoria discreta , entonces su función generadora ordinaria se denomina función generadora de probabilidad . $${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{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 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 un análogo directo con la relación de recurrencia anterior. En este punto de vista, el término factorial n ! es meramente un contratérmino para normalizar el operador de derivada que actúa sobre x ⁿ .

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 Nótese que 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. $${\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 para números enteros n ≥ 1 están relacionados por la suma de los divisores . El artículo principal proporciona varios ejemplos más clásicos, o al menos bien conocidos, relacionados con funciones aritméticas especiales en teoría de números . Como ejemplo de una identidad de serie de Lambert no dada en el artículo principal, podemos mostrar que para | x |, | xq | < 1 tenemos que ^[4] $${\displaystyle b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x)}$$ $${\displaystyle b_{n}=\sum _{d|n}a_{d}.}$$ $${\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 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 de campanas

La serie de Bell de una secuencia a _n es una expresión en términos tanto de un indeterminado x como de un primo p y está dada por: ^[5] $${\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 suelen clasificarse como funciones generadoras, aunque no son estrictamente series de potencias formales. La función generadora de la serie de Dirichlet de una secuencia a _n es: ^[6] $${\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 una función multiplicativa , en cuyo caso tiene una expresión de producto de Euler ^[7] 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 series de Lambert anteriores y sus DGF. Es decir, podemos demostrar que: si y solo si donde ζ ( s ) es la función zeta de Riemann . ^[8] $${\displaystyle [x^{n}]\operatorname {LG} (a_{n};x)=b_{n}}$$ $${\displaystyle \operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s),}$$

La secuencia a _k generada por una función generadora de series de Dirichlet (DGF) correspondiente a: tiene la función generadora ordinaria: $${\displaystyle \operatorname {DG} (a_{k};s)=\zeta (s)^{m}}$$ $${\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 de secuencias polinómicas

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: donde p _n ( x ) es una secuencia de polinomios y f ( t ) es una función de una forma determinada. Las secuencias de Sheffer se generan de manera similar. Consulte el artículo principal Polinomios de Appell generalizados para obtener más información. $${\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}}$$

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

• Polinomios de Appell
• Polinomios de Chebyshev
• Polinomios diferenciales
• Polinomios de Appell generalizados
• polinomios de q -diferencia

Otras funciones generadoras

Otras secuencias generadas por funciones generadoras más complejas incluyen:

• Funciones generadoras de exponentes 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 " ^[9] define una clase generalizada de secuencias de polinomios de convolución por sus funciones generadoras especiales de la forma para alguna función analítica F con una expansión en serie de potencias tal que F (0) = 1 . $${\displaystyle F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n},}$$

Decimos que una familia de polinomios, f ₀ , f ₁ , f ₂ , ... , forma una familia de convolución si deg 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 es equivalente 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 polinomiales de convolución dadas por donde 𝓕 _t ( z ) está implícitamente definida por una ecuación funcional de la forma 𝓕 _t ( z ) = F ( x 𝓕 _t ( z ) ^t ) . Además, podemos usar métodos matriciales (como en la referencia) para demostrar que dadas dos secuencias polinomiales de convolución, ⟨ f _n ( x ) ⟩ y ⟨ g _n ( x ) ⟩ , con respectivas funciones generadoras correspondientes, F ( z ) ^x y G ( z ) ^x , entonces para un t arbitrario tenemos la identidad ${\displaystyle t\in \mathbb {C} }$ $${\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n}\right]{\mathcal {F}}_{t}(z)^{x},}$$ $${\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).}$$

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

Funciones generadoras ordinarias

Ejemplos de secuencias simples

Los polinomios son un caso especial de funciones generadoras ordinarias, correspondientes a sucesiones finitas o, equivalentemente, sucesiones que se anulan después de cierto punto. Su importancia radica en que muchas sucesiones 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 sucesión 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 ninguna 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.

A partir de esta expresión se pueden derivar fácilmente expresiones para la función generadora ordinaria de otras sucesiones. Por ejemplo, la sustitución x → ax da la función generadora para la sucesión 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 sigue 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 huecos 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 hallar la derivada de ambos lados con respecto a x y hacer un cambio de variable móvil n → n + 1 , se ve que los coeficientes forman la secuencia 1, 2, 3, 4, 5, ... , por lo que se 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}
₂) , 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 a distinto de cero , 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 la 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 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]+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 ^{[10] [11]} $${\displaystyle n^{m}=\sum _{j=0}^{m}{\begin{Bmatrix}m\\j\end{Bmatrix}}{\frac {n!}{(n-j)!}},}$$

dónde {^no
_k} denotan 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 podemos formar las funciones generadoras análogas sobre las potencias integrales m que generalizan 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 ^[12] $${\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 puede expresarse como una función racional (la relació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. Por el contrario, cada 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 la fracción (por lo que se pueden leer directamente). Esta observación muestra que es fácil resolver funciones generadoras de secuencias definidas por una ecuación lineal en diferencias finitas con coeficientes constantes y, por lo tanto, fórmulas explícitas en 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 funciones generadoras.

También observamos que la clase de funciones generadoras racionales corresponde precisamente a las funciones generadoras que enumeran secuencias cuasi-polinomiales de la forma ^[13] $${\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 función generadora diagonal correspondiente , $${\displaystyle \operatorname {diag} (F):=\sum _{n=0}^{\infty }f(n,n)z^{n},}$$

es algebraica . Por ejemplo, si dejamos ^[14] $${\displaystyle F(s,t):=\sum _{i,j\geq 0}{\binom {i+j}{i}}s^{i}t^{j}={\frac {1}{1-s-t}},}$$

Entonces, el coeficiente diagonal de la función generadora está dado 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 de Euler-Maclaurin ligeramente más general ) de una secuencia con función generadora ordinaria G ( a _n ; x ) tiene la función generadora porque ⁠ $${\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )}$$ $${\displaystyle G(a_{n};x)\cdot {\frac {1}{1-x}}}$$1/1 − x⁠ es la función generadora ordinaria para la secuencia (1, 1, ...) . Consulte también la sección sobre convoluciones en la sección de aplicaciones de este artículo a continuación para obtener más ejemplos de resolución de problemas con convoluciones de funciones generadoras e interpretaciones.

Cambio de índices de secuencia

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 respectivas de series de potencias 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 cambio se realizan k diferenciaciones en secuencia, el efecto es multiplicar por el 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 }}k\in \mathbb {N} .}$$

Usando los números de Stirling del segundo tipo , que se pueden convertir en otra fórmula para multiplicar por de la siguiente manera (ver el artículo principal sobre transformaciones de funciones generadoras ): ${\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 de la serie zeta y sus generalizaciones definidas como una transformación basada en derivadas de funciones generadoras o, alternativamente, mediante y realizando una transformación integral en la función generadora de secuencia. Aquí se analizan las operaciones relacionadas con la realización de la integración fraccionaria en una función generadora de secuencia .

Enumeración de 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 (ver el artículo principal sobre transformaciones ). Para a = 2 , esta 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}}}$$

De manera más general, supongamos que a ≥ 3 y que ω _a = exp ⁠2πi​/a⁠ denota laraíz primitiva a de la unidad . Entonces, como aplicación de la transformada de Fourier discreta , tenemos la fórmula ^[15] $${\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 , otra fórmula útil que proporciona progresiones aritméticas de base algo invertidas (que efectivamente repiten cada coeficiente m veces) se genera mediante la identidad ^[16] $${\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}).}$$

PAG-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 ^[17] $${\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, . Equivalentemente, 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)}$

Puesto que podemos despejar denominadores si es necesario en la ecuación anterior, podemos suponer que las funciones, c _i ( z ) son polinomios en z . Así, 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 de producto de Hadamard ⊙ sobre funciones generadoras.

Ejemplos

Las funciones e ^z , log z , cos z , arcsin z , , la función dilogarítmica 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/n +1⁠ (^{2 n}
_n) y f _n ≔ ⁠2 ⁿ/n ² + 1⁠ , donde secuencias comoy log n no son P -recursivas debido a la naturaleza de las singularidades en sus funciones generadoras correspondientes. De manera similar, funciones con infinitas singularidades como tan z , sec z y Γ( z ) no sonfunciones holonómicas. ${\displaystyle {\sqrt {n}}}$

Software para trabajar conPAG-secuencias 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 del RISC Combinatorics Group. A pesar de ser en su mayoría de código cerrado, las herramientas particularmente poderosas en este paquete de software son proporcionadas por el Guesspaquete para 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 de forma cerrada para P -recurrencias que involucran números armónicos generalizados . ^[18] Otros paquetes enumerados en este sitio RISC en particular están destinados a trabajar específicamente con funciones generadoras holonómicas .

Relación con la transformada de Fourier de tiempo discreto

Cuando la serie converge absolutamente , la transformada de Fourier de tiempo discreto de la secuencia es a ₀ , a ₁ , ... . $${\displaystyle G\left(a_{n};e^{-i\omega }\right)=\sum _{n=0}^{\infty }a_{n}e^{-i\omega n}}$$

Crecimiento asintótico de una secuencia

En cálculo, la tasa de crecimiento de los coeficientes de una serie de potencias se puede utilizar a menudo para deducir un radio de convergencia para la serie de potencias. También puede darse el caso inverso: 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 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 uno de A ( x ) y B ( x ) es una función que es analítica a un radio de convergencia mayor que r (o es entero ), y donde B ( r ) ≠ 0 entonces usando la función gamma , un coeficiente binomial o un coeficiente multiconjunto . $${\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 iterar para generar varios términos en una serie asintótica para un _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 se puede buscar entonces a través del hallazgo de A , B , α , β y r 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_​/¡no !⁠ que crece según estas fórmulas asintóticas. En general, 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 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 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 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

La función generadora en varias variables se puede generalizar a matrices con múltiples índices. Estos ejemplos de suma doble no polinómica se denominan funciones generadoras multivariadas o funciones supergeneradoras . Para dos variables, se las suele denominar funciones generadoras bivariadas .

Caso bivariado

La función generadora ordinaria de una matriz bidimensional a _{m , n} (donde n y m son números naturales) es: Por ejemplo, dado que (1 + x ) ⁿ es la función generadora ordinaria para coeficientes binomiales para un n fijo , se puede solicitar una función generadora bivariada que genere los coeficientes binomiales ( $${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.}$$^no
_k) para todos los k y n . Para ello, considere (1 + x ) ⁿ como una secuencia en n , y encuentre la función generadora en y que tiene estos valores de secuencia como coeficientes. Dado que la función generadora para un ⁿ es: la función generadora para los coeficientes binomiales es: Otros ejemplos de este tipo incluyen las siguientes funciones generadoras de dos variables para los coeficientes binomiales , los números de Stirling y los números de Euler , donde ω y z denotan las dos variables: ^[19] $${\displaystyle {\frac {1}{1-ay}},}$$ $${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}.}$$ $${\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}}}$$

Caso multivariado

Las funciones generadoras multivariadas surgen en la práctica al calcular el número de tablas de contingencia de números enteros no negativos con totales de filas y columnas especificados. Supongamos que la tabla tiene r filas y c 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: en: $${\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}}}.}$$

Representación mediante fracciones continuas (tipo Jacobi)Yo-fracciones)

Definiciones

Las expansiones de fracciones continuas de tipo Jacobi (formales) y de tipo Stieltjes ( fracciones J y fracciones S , respectivamente) cuyos convergentes racionales h representan 2 series de potencias precisas de orden 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 ( fracciones J ) se expanden como en la siguiente ecuación y tienen las siguientes expansiones de series de potencias correspondientes con respecto a z para algunas secuencias de componentes específicas y dependientes de la aplicación, {ab _i } y { c _i } , donde z ≠ 0 denota la variable formal en la segunda expansión de series de potencias que se da a continuación: ^[21] $${\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 abreviadamente 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 enteros p , q ≥ 0 , tenemos una relación de 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 layolas funciones convergentes

Para h ≥ 0 (aunque en la práctica cuando h ≥ 2 ), podemos definir los h ésimos convergentes racionales a la fracción J infinita, 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 por 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 de 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 los ejemplos contenidos en la tabla siguiente.

Ejemplos

La siguiente tabla proporciona ejemplos de fórmulas de forma cerrada para las secuencias de componentes encontradas computacionalmente (y posteriormente probadas correctas en las referencias citadas ^[22] ) en varios casos especiales de las secuencias prescritas, j _n , generadas por las expansiones generales de las J -fracciones definidas en la primera subsección. Aquí definimos 0 < | a |, | b |, | q | < 1 y los parámetros y x como 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 J -fracciones de tipo Jacobi dadas anteriormente son en general diferentes de los de las expansiones de series de potencias correspondientes que definen las funciones generadoras ordinarias de estas secuencias.

Ejemplos

Números cuadrados

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

donde ζ ( s) es la función zeta de Riemann .

Aplicaciones

Las funciones generadoras se utilizan para:

• Encuentre una fórmula cerrada para una secuencia dada en una relación de recurrencia, por ejemplo, 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.
• Explorar el comportamiento asintótico de las secuencias.
• Demostrar identidades que involucran secuencias.
• Resolver problemas de enumeración en combinatoria y codificar sus soluciones. Los polinomios de Rook son un ejemplo de aplicación en combinatoria.
• Evaluar sumas infinitas.

Varias técnicas: Evaluación de sumas y solución de otros problemas con funciones generadoras

Ejemplo 1: Fórmula para la suma 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 = Σ^nk _=
0 a _k . Entonces sabemos que S ( z ) = ⁠A ( z )/1 − z⁠ para las funciones generadoras ordinarias correspondientes.

Por ejemplo, podemos manipular donde H _k = 1 + ⁠ $${\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}\,,}$$1/2⁠ + ⋯ + ⁠1/a⁠ son los números armónicos . Sea la función generadora ordinaria de los números armónicos. Entonces y por lo tanto $${\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 la convolución con el numerador se obtiene lo que también se puede escribir como $${\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 de uso de funciones generadoras para relacionar secuencias y manipular sumas, para una secuencia arbitraria ⟨ f _n ⟩ definimos las dos secuencias de sumas para todo n ≥ 0 y buscamos expresar las segundas sumas en términos de la primera. Sugerimos un enfoque mediante funciones generadoras. $${\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}}}$$

Primero, usamos la transformada binomial para escribir la función generadora para la primera suma como $${\displaystyle S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}}\right).}$$

Dado que la función generadora para la secuencia ⟨ ( n + 1)( n + 2)( n + 3) f _n ⟩ está dada por podemos escribir la función generadora para la segunda suma definida anteriormente en la forma $${\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 para a ( z ) = 6(1 − 3 z ) ³ , b ( z ) = 18(1 − 3 z ) ³ , c ( z ) = 9(1 − 3 z ) ³ , y d ( z ) = (1 − 3 z ) ³ , donde (1 − 3 z ) ³ = 1 − 9 z + 27 z ² − 27 z ³ . $${\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),}$$

Finalmente, se deduce que podemos expresar las segundas sumas a través de las primeras sumas en 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 recursivas entre sí

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 obtener bonitas imágenes de series de funciones generadoras). En particular, supongamos que buscamos el número total de formas (denotado U _n ) para cubrir un rectángulo de 3 por n con piezas de dominó de 2 por 1 sin marcar. Sea la secuencia auxiliar, V _n , definida como el número de formas de cubrir un rectángulo de 3 por n , menos la sección de las esquinas del rectángulo completo. Buscamos usar estas definiciones para dar una fórmula de forma cerrada para U _n sin descomponer aún 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 mutuamente recursivas , para nuestras dos secuencias cuando n ≥ 2 definido 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}}}$$

Puesto que tenemos que para todos los enteros m ≥ 0 , las funciones generadoras desplazadas por índice satisfacen ^{[nota 1]} podemos usar las condiciones iniciales especificadas anteriormente y las dos relaciones de recurrencia anteriores para ver que tenemos las siguientes dos ecuaciones que relacionan las funciones generadoras para estas secuencias dadas por lo que entonces implica al resolver el sistema de ecuaciones (y este es el truco particular de nuestro método aquí) que $${\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 para todos los enteros n ≥ 0 . También notamos que la misma técnica de función generadora desplazada aplicada a la recurrencia de segundo orden para los números de Fibonacci es el ejemplo prototípico de uso de funciones generadoras para resolver relaciones de recurrencia en una variable ya cubierta, o al menos insinuada, en la subsección sobre funciones racionales dada anteriormente. $${\displaystyle U_{2n}=\left\lceil {\frac {\left(2+{\sqrt {3}}\right)^{n}}{3-{\sqrt {3}}}}\right\rceil \,,}$$

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 ).

1. Consideremos 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 -fold de una secuencia consigo misma para algún entero positivo m ≥ 1 (vea el ejemplo a continuación 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 ^[23] si X e Y son independientes. De manera similar, el número de formas de pagar n ≥ 0 centavos en denominaciones de monedas de valores en el conjunto {1, 5, 10, 25, 50} (es decir, en centavos, monedas de cinco centavos, de diez centavos, de veinticinco centavos y de medio dólar, respectivamente) se genera por el producto y, además, si permitimos que los n centavos se paguen en monedas de cualquier denominación entera positiva, llegamos a la generación para el número de tales combinaciones de cambio que se generan por la función generadora de la función de partición expandida por el producto infinito del símbolo q -Pochhammer de $${\displaystyle G_{X+Y}(z)=G_{X}(z)G_{Y}(z)\,,}$$ $${\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}}},}$$ $${\displaystyle \prod _{n=1}^{\infty }\left(1-z^{n}\right)^{-1}\,.}$$

Ejemplo: Función generadora para los números catalanes

Un ejemplo en el que las convoluciones de funciones generadoras son útiles nos permite resolver una función específica en forma cerrada que representa la función generadora ordinaria para los números Catalan , 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 y, por lo tanto, tiene una función generadora convolucionada correspondiente, C ( z ) , que satisface $${\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\,,}$$ $${\displaystyle C(z)=z\cdot C(z)^{2}+1\,.}$$

Como C (0) = 1 ≠ ∞ , llegamos entonces 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}\,.}$$

Nótese que la primera ecuación que define implícitamente C ( z ) arriba implica lo que luego conduce a otra expansión de fracción continua "simple" (de forma) de esta función generadora. $${\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 grafo 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 una única arista al siguiente vértice k + 1 para todo 1 ≤ k < n . ^[24] Hay un abanico de orden uno, tres abanicos de orden dos, ocho abanicos de orden tres, y así sucesivamente. Un árbol de expansión es un subgrafo de un grafo que contiene todos los vértices originales y que contiene suficientes aristas para hacer que este subgrafo esté conectado, pero no tantas aristas como para que haya un ciclo en el subgrafo. Nos preguntamos cuántos árboles de expansión 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 adyacentes de vértices. 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 sobre las m convoluciones de la secuencia g _n = n = [ z ⁿ ] ⁠el/(1 − z ) ²⁠ para m ≔ 1, 2, 3, 4. De manera más general, podemos escribir una fórmula para esta secuencia como de la cual vemos que la función generadora ordinaria para esta secuencia está dada por la siguiente suma de convoluciones como de la cual podemos extraer una fórmula exacta para la secuencia tomando la expansión en fracción parcial de la última función generadora. $${\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}}}\,,}$$

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 utilizada para evaluar explícitamente soluciones a dichas 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 admite una solución única en , que satisface ${\textstyle \phi (z)\in C[[z]]}$ $${\displaystyle T(z)=z\phi (T(z))}$$ ${\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 en . ${\displaystyle [z^{n}]F(z)}$ ${\displaystyle z^{n}}$ ${\displaystyle F(z)}$

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

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

Mediante la expansión del teorema binomial, para , la fórmula devuelve . Esto es lo esperado, ya que se puede demostrar que la cantidad de hojas de un árbol binario es una más que la cantidad de sus nodos internos, por lo que la suma total siempre debería ser un número impar. Sin embargo, para , 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 simplemente se convierte en el ^número catalán. ${\displaystyle n}$ ${\displaystyle n}$

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 método de los "parámetros libres" es otro método (denominado "aceite de serpiente" por H. Wilf) para evaluar estas sumas.

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

Por ejemplo, si queremos calcular, podemos tratar a n como un parámetro "libre" y establecer $${\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}\,,}$$ $${\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 eszm ^{+ 2k​}/(1 − z ) ^{m + 2 k + 1}⁠ . Por lo tanto $${\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 utilizar el mismo método nuevamente para la suma, pero esta vez tomando m como parámetro libre en lugar de n . De esta manera, 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 sumatoria 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} . Por lo tanto $${\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}}}$$

Por lo tanto obtenemos para m ≥ 1 como antes. $${\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}}\,,}$$

Las funciones generadoras demuestran 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 enteros n (nótese que no necesitamos suponer que m es un entero aquí—puede muy bien tener un valor polinomial en algún indeterminado x , 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 casos particulares fijos de valores enteros m ≥ 2 . Por ejemplo, podemos probar que los números de Euler , satisfacen la siguiente congruencia módulo 3: ^[25] $${\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}}\,.}$$

Un método útil para obtener congruencias para secuencias enumeradas por funciones generadoras especiales módulo cualquier número entero (es decir, no solo potencias primos p ^k ) se da en la sección sobre representaciones de fracciones continuas de funciones generadoras ordinarias (incluso no convergentes) por J -fracciones anterior. 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 Lecciones sobre funciones generadoras de Lando, como sigue:

Teorema: congruencias para series generadas por desarrollos de fracciones continuas  —  Supóngase que la función generadora A ( z ) está representada por una fracción continua infinita de la forma y que A _p ( z ) denota la p ésima convergente a este desarrollo de fracción continua definida de manera que a _n = [ z ⁿ ] A _p ( z ) para todo 0 ≤ n < 2 p . Entonces: $${\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 }}}}}}}}$$

1. la función A _p ( z ) es racional para todo p ≥ 2 donde suponemos que se cumple uno de los criterios de divisibilidad de p | p ₁ , p ₁ p ₂ , p ₁ p ₂ p ₃ , es decir, p | p ₁ p ₂ ⋯ p _k para algún k ≥ 1 ; y
2. Si el 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 para sus coeficientes. Citamos los dos ejemplos específicos siguientes que derivan congruencias de casos especiales para los números de Stirling de primera clase y para la función de partición p ( n ) que muestran la versatilidad de las funciones generadoras 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 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 módulo 2, estas funciones generadoras de productos finitos satisfacen cada una

$${\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 demuestra que [^no
_k] 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 serie de potencias generan las expansiones de muchas funciones especiales y enumeramos funciones de partición. En particular, recordamos que la función de partición p ( n ) se genera mediante el producto infinito recíproco del símbolo q -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: ^[26] $${\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 muy elemental de la primera de estas congruencias enumeradas anteriormente.

En primer lugar, observamos que en la función generadora de coeficientes binomiales todos los coeficientes son divisibles por 5 excepto aquellos que corresponden a las potencias 1, z ⁵ , z ¹⁰ , ... y además en esos casos el resto del coeficiente es 1 módulo 5. Por lo tanto, o equivalentemente, se sigue que $${\displaystyle {\frac {1}{(1-z)^{5}}}=\sum _{i=0}^{\infty }{\binom {4+i}{4}}z^{i}\,,}$$ $${\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 infinitas expansiones del producto de la misma se puede demostrar que el coeficiente de z ^{5 m + 5} en z · ((1 − z )(1 − z ² )⋯) ⁴ es divisible por 5 para todo m . ^[27] Finalmente, dado que podemos igualar los coeficientes de z ^{5 m + 5} en las ecuaciones anteriores para demostrar nuestro resultado de congruencia deseado, es decir, que p (5 m + 4) ≡ 0 (mod 5) para todo m ≥ 0 . $${\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}}}\,,}$$ $${\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}}}$$

Transformaciones de funciones generadoras

Existen varias transformaciones de funciones generadoras que brindan 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 OGF de secuencia (consulte transformaciones integrales ) o sumas ponderadas sobre las derivadas de orden superior de estas funciones (consulte 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 entonces la función generadora para las expresiones de suma modificadas está dada por ^[28] (ver también la transformada binomial y la transformada de Stirling ). $${\displaystyle s_{n}:=\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}a_{k}\,}$$ $${\displaystyle S(z)={\frac {z^{m}}{(1-z)^{m+1}}}A\left({\frac {z}{(1-z)^{2}}}\right)}$$

También existen fórmulas integrales para convertir entre la OGF de una secuencia, F ( z ) , y su función generadora exponencial, o EGF, F̂ ( z ) , y viceversa, dadas 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 .

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 Generatingfunctionology de Wilf 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 no está completa en absoluto. ^[29]

Véase también

• Función generadora de momentos
• Función generadora de probabilidad
• Transformación de función generadora
• Teorema de reciprocidad de Stanley
• Partición de enteros
• Principios combinatorios
• Tamizado cíclico
• Transformada Z
• Cálculo umbral
• Monedas en una fuente

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. 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.
2. Knuth, Donald E. (1997). "§1.2.9 Generación de funciones". Algoritmos fundamentales . El arte de la programación informática . Vol. 1 (3.ª ed.). Addison-Wesley. ISBN 0-201-89683-4.
3. Flajolet y Sedgewick 2009, pág. 95
4. "Identidad de la serie de Lambert". Desbordamiento de matemáticas . 2017.
5. 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, MR  0434929, Zbl  0335.10001págs. 42-43
6. Wilf 1994, pág. 56
7. Wilf 1994, pág. 59
8. Hardy, GH; Wright, EM; Heath-Brown, DR; Silverman, JH (2008). Introducción a la teoría de números (6.ª ed.). Oxford University Press. pág. 339. ISBN 9780199219858.
9. Knuth, DE (1992). "Polinomios de convolución". Mathematica J . 2 : 67–78. arXiv : math/9207221 . Código Bibliográfico :1992math......7221K.
10. Spivey, Michael Z. (2007). "Sumas combinatorias y diferencias finitas". Matemáticas discretas . 307 (24): 3130–3146. doi : 10.1016/j.disc.2007.03.052 . MR  2370116.
11. Mathar, RJ (2012). "Otra tabla de integrales". arXiv : 1207.5845 [math.CA].v4 ec. (0,4)
12. Graham, Knuth y Patashnik 1994, Tabla 265 en §6.1 para identidades de suma finita que involucran los triángulos de números de Stirling.
13. Lando 2003, §2.4
14. Ejemplo de Stanley, Richard P.; Fomin, Sergey (1997). "§6.3". Combinatoria enumerativa: volumen 2. Cambridge Studies in Advanced Mathematics. Vol. 62. Cambridge University Press. ISBN 978-0-521-78987-5.
15. Knuth 1997, §1.2.9
16. Solución de Graham, Knuth y Patashnik 1994, pág. 569, ejercicio 7.36
17. Flajolet y Sedgewick 2009, §B.4
18. Schneider, C. (2007). "La suma simbólica ayuda a la combinatoria". Sém. Lothar. Combin . 56 : 1–36.
19. Véase el uso de estos términos en Graham, Knuth y Patashnik 1994, §7.4 sobre funciones generadoras de secuencias especiales.
20. Good, IJ (1986). "Sobre aplicaciones de distribuciones de Dirichlet simétricas y sus mezclas a tablas de contingencia". Anales de Estadística . 4 (6): 1159–1189. doi : 10.1214/aos/1176343649 .
21. Para obtener información más completa sobre las propiedades de las J -fracciones, 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.
    • Wall, HS (2018) [1948]. Teoría analítica de fracciones continuas. Dover. ISBN 978-0-486-83044-5.
22. Ver los siguientes artículos:
    • Schmidt, Maxie D. (2016). "Fracciones continuas para funciones generadoras de series cuadradas". arXiv : 1612.02778 [math.NT].
    • — (2017). "Fracciones continuas de tipo Jacobi para las funciones generadoras ordinarias de funciones factoriales generalizadas". Revista de secuencias enteras . 20 . arXiv : 1610.09691 . 17.3.4.
    • — (2017). "Fracciones continuas de tipo Jacobi y congruencias para coeficientes binomiales módulo enteros h ≥ 2". arXiv : 1702.01374 [math.CO].
23. Graham, Knuth y Patashnik 1994, §8.3
24. Graham, Knuth y Patashnik 1994, Ejemplo 6 en §7.3 para 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.
25. Lando 2003, §5
26. Hardy y otros, 2008, §19.12
27. Hardy, GH; Wright, EM Una introducción a la teoría de números .pág. 288, tomo 361
28. Graham, Knuth y Patashnik 1994, pág. 535, ejercicio 5.71
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, Martin (2007). Un curso de enumeración. Textos de posgrado en matemáticas. Vol. 238. Springer. ISBN 978-3-540-39035-0.
• Doubilet, Peter; Rota, Gian-Carlo ; Stanley, Richard (1972). "Sobre los fundamentos de la teoría combinatoria. VI. La idea de la función generadora". Actas del Sexto Simposio de Berkeley sobre Estadística Matemática y Probabilidad . 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 . Academic Press. págs. 83–134. ISBN. 0-12-596650-4.Zbl 0328.05007  .
• Flajolet, Philippe ; Sedgewick, Robert (2009). Combinatoria analítica . Cambridge University Press. 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: Funciones generadoras". Matemáticas concretas. Fundamentos de la informática (2.ª ed.). Addison-Wesley. págs. 320–380. ISBN 0-201-55802-5.Zbl 0836.00001  .
• Lando, Sergei K. (2003). Lecciones sobre funciones generadoras. American Mathematical Society. ISBN 978-0-8218-3481-7.
• Wilf, Herbert S. (1994). Función generadora (2.ª ed.). Academic Press. 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 moneda en cut-the-knot
• "Funciones generadoras" por Ed Pegg Jr. , Wolfram Demonstrations Project , 2007.