En matemáticas , una función de generación es una forma de codificar una secuencia infinita de números ( un n ) tratándolos como los coeficientes de una serie formal . Esta serie se denomina función generadora de la secuencia. A diferencia de una serie ordinaria, no se requiere que la serie de potencias formal converja : de hecho, la función generadora no se considera realmente una función y la "variable" permanece indeterminada . Las funciones generadoras fueron introducidas por primera vez por Abraham de Moivreen 1730, para resolver el problema general de recurrencia lineal. [1] Se puede generalizar a series de potencias formales en más de un indeterminado, para codificar información sobre arreglos de números infinitos y multidimensionales.
Hay varios tipos de funciones generadoras, incluidas funciones generadoras ordinarias , funciones generadoras exponenciales , series de Lambert , series de Bell y series de Dirichlet ; las 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 se pueden manejar puede diferir considerablemente. La función generadora particular, si la hay, que sea más útil en un contexto dado, dependerá de la naturaleza de la secuencia y de los detalles del problema que se aborde.
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 de la x indeterminada pueden involucrar 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 se definen 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 puede evaluarse en valores concretos (suficientemente pequeños) de x , y que tiene la serie formal como su expansión de serie ; esto explica la designación "funciones generadoras". Sin embargo, no se requiere que dicha interpretación sea posible, porque no se requieren series formales para dar una serie convergente cuando se sustituye x por un valor numérico distinto de cero . Además, no todas las expresiones que son significativas como funciones de x lo son como expresiones que designan series formales; por ejemplo, las potencias negativas y fraccionarias de x son ejemplos de funciones que no tienen una serie de potencias formal correspondiente.
Las funciones generadoras no son funciones en el sentido formal de un mapeo de un dominio a un codominio . Las funciones generadoras a veces se denominan series generadoras , [2] en el sentido de que se puede decir que una serie de términos es el generador de su secuencia de coeficientes de términos.
Definiciones
Una función generadora es un dispositivo algo similar a una bolsa. En lugar de llevar muchos objetos pequeños por separado, lo que podría ser vergonzoso, los ponemos todos en una bolsa, y luego solo tenemos un objeto para llevar, la bolsa.
La función generadora ordinaria se puede generalizar a matrices con múltiples índices. Por ejemplo, la función ordinaria de generación de una matriz de dos dimensiones de una m, n (donde n y m son números naturales) es
Función generadora exponencial (EGF)
La función de generación exponencial de una secuencia de un n es
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]
Función generadora de Poisson
La función generadora de Poisson de una secuencia a n es
Los coeficientes de la serie de Lambert en las expansiones de la serie de potencias para enteros están relacionados por la suma del divisor . El artículo principal proporciona varios ejemplos más clásicos, o al menos bien 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 el primer término no estaría definido de otro modo.
Serie campana
La serie de Bell de una secuencia de un n es una expresión tanto en términos de una indeterminada x y un primer p y está dada por [4]
Funciones generadoras de la serie Dirichlet (DGF)
Las series de Dirichlet formales a menudo se clasifican como funciones generadoras, aunque no son series de potencia estrictamente formales. La función generadora de la serie de Dirichlet de una secuencia a n es [5]
La función de generación de series de Dirichlet es especialmente útil cuando una n es una función multiplicativa , en cuyo caso tiene una expresión del producto de Euler [6] en términos de la serie de Bell de la función.
La idea de generar funciones se puede extender a secuencias de otros objetos. Así, por ejemplo, las secuencias polinómicas de tipo binomial son generadas por
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 forma similar. Consulte el artículo principal sobre polinomios de Appell generalizados para obtener más información.
Funciones generadoras ordinarias
Ejemplos de funciones generadoras para secuencias simples
Los polinomios son un caso especial de funciones generadoras ordinarias, correspondientes a secuencias finitas o, de manera equivalente, secuencias que desaparecen después de cierto punto. Estos son importantes porque muchas secuencias finitas pueden interpretarse de manera útil como funciones generadoras, como el polinomio de Poincaré y otras.
Una función generadora fundamental es la de la secuencia constante 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., cuya función generadora ordinaria es la serie geométrica
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 verificando que el resultado es la serie de potencia constante 1 (en otras palabras, que todos los coeficientes excepto el de x 0 son iguales a 0) . Además, no puede haber otra serie de potencia con esta propiedad. Por tanto, el lado izquierdo designa el inverso multiplicativo de 1 - x en el anillo de la serie de potencias.
Las expresiones para la función generadora ordinaria de otras secuencias se derivan fácilmente de esta. Por ejemplo, la sustitución x → ax da la función generadora para la secuencia geométrica 1, a , a 2 , a 3 , ... para cualquier constante a :
(La igualdad también se deriva directamente del hecho de que el lado izquierdo es la expansión de la serie de Maclaurin del lado derecho). En particular,
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, .... se obtiene la generación función
Al elevar al cuadrado la función generadora inicial, o al encontrar la derivada de ambos lados con respecto ax y hacer un cambio en la variable de ejecución n → n + 1, se ve que los coeficientes forman la secuencia 1, 2, 3, 4, 5, ..., entonces uno tiene
De manera más general, para cualquier entero no negativo k y valor real distinto de cero a , es cierto que
Desde
se puede encontrar la función generadora ordinaria para la secuencia 0, 1, 4, 9, 16, ... de números cuadrados por combinación lineal de secuencias generadoras de coeficientes binomiales:
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:
Por inducción, podemos mostrar de manera similar para enteros positivos que [8] [9]
dónde denotar los números de Stirling del segundo tipo y donde la función generadora, de modo que podamos formar las funciones generadoras análogas sobre la integral -ésimas potencias generalizando el resultado en el caso cuadrado anterior. En particular, dado que podemos escribir, podemos aplicar una identidad de suma finita bien conocida que involucra los números de Stirling para obtener que [10]
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 lineal recursiva con coeficientes constantes; esto generaliza los ejemplos anteriores. A la inversa, 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 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 tanto, para fórmulas explícitas de forma cerrada para los coeficientes de estas funciones generadoras. El ejemplo prototípico aquí es derivar la fórmula de Binet para los números de Fibonacci mediante técnicas de generación de funciones.
También notamos que la clase de funciones generadoras racionales corresponde precisamente a las funciones generadoras que enumeran secuencias cuasi-polinomiales de la forma [11]
donde las raíces recíprocas, , son escalares fijos y donde es un polinomio en para todos .
En general, los productos de funciones racionales de Hadamard producen funciones generadoras racionales. Del mismo modo, sies una función generadora racional bivariada, entonces su función generadora diagonal correspondiente ,, es algebraico . Por ejemplo, si dejamos [12]
entonces la función generadora de coeficientes diagonales de esta función generadora viene dada por la conocida fórmula OGF
Este resultado se calcula de muchas maneras, incluida la fórmula integral de Cauchy o la integración de contorno , tomando residuos complejos o mediante manipulaciones directas de series de potencias formales en dos variables.
Operaciones sobre funciones generadoras
La multiplicación produce convolución
La multiplicación de funciones generadoras ordinarias produce una convolución discreta (el producto de Cauchy ) de las secuencias. Por ejemplo, la secuencia de sumas acumulativas (compárese con la fórmula ligeramente más general de Euler-Maclaurin )
de una secuencia con función generadora ordinaria G ( a n ; x ) tiene la función generadora
porque 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.
Índices de secuencia de cambio
Para enteros , tenemos las siguientes dos identidades análogas para las funciones generadoras modificadas que enumeran las variantes de secuencia desplazada de y , respectivamente:
Diferenciación e integración de funciones generadoras
Tenemos las siguientes expansiones de series de potencia respectivas para la primera derivada de una función generadora y su integral:
La operación de diferenciación-multiplicación de la segunda identidad se puede repetir veces para multiplicar la secuencia por , pero eso requiere alternar entre diferenciación y multiplicación. Si en cambio haciendo diferenciaciones en secuencia, el efecto es multiplicar por el º caer factorial :
Usando los números de Stirling del segundo tipo , que se pueden convertir en otra fórmula para multiplicar porde la siguiente manera (consulte el artículo principal sobre la generación de transformaciones de funciones ):
Una inversión de orden negativo de esta fórmula de potencias de secuencia correspondiente a la operación de integración repetida se define mediante la transformación en serie zeta y sus generalizaciones se definen como una transformación basada en derivadas de funciones generadoras , o alternativamente en términos de términos mediante la realización de una transformación integral en la secuencia. función generadora. Las operaciones relacionadas de realizar la integración fraccional en una función generadora de secuencia se analizan aquí .
Enumerar progresiones aritméticas de secuencias
En esta sección damos fórmulas para generar funciones enumerando la secuencia dada una función generadora ordinaria dónde , , y (ver el artículo principal sobre transformaciones ). Para, esta es simplemente la descomposición familiar de una función en partes pares e impares (es decir, potencias pares e impares):
De manera más general, suponga que y eso denota el la raíz primitiva de la unidad . Entonces, como una aplicación de la transformada discreta de Fourier , tenemos la fórmula [13]
Para enteros , otra fórmula útil que proporciona progresiones aritméticas algo invertidas , repitiendo efectivamente cada coeficientetiempos - son generados por la identidad [14]
Secuencias P-recursivas y funciones generadoras holonómicas
Definiciones
Una serie de poder formal (o función) se dice que es holonómico si satisface una ecuación diferencial lineal de la forma [15]
donde los coeficientes están en el campo de las funciones racionales, . Equivalentemente, es holonómico si el espacio vectorial sobre abarcado por el conjunto de todas sus derivadas es de dimensión finita.
Dado que podemos borrar denominadores si es necesario en la ecuación anterior, podemos suponer que las funciones, son polinomios en . Por tanto, podemos ver una condición equivalente de que una función generadora es holonómica si sus coeficientes satisfacen una P-recurrencia de la forma
para todos lo suficientemente grande y donde el son polinomios fijos de grado finito en . En otras palabras, las propiedades de que una secuencia sea P-recursiva y tenga una función generadora holonómica son equivalentes. Las funciones holonómicas están cerradas bajo la operación del producto Hadamard sobre la generación de funciones.
Ejemplos de
Las funciones , , , , , la función dilogaritmo, las funciones hipergeométricas generalizadas y las funciones definidas por la serie de potencias y el no convergente son todos holonómicos. Ejemplos de secuencias P-recursivas con funciones generadoras holonómicas incluyen y , donde secuencias como y no son P-recursivas debido a la naturaleza de las singularidades en sus funciones generadoras correspondientes. De manera similar, funciones con un número infinito de singularidades como, , y no son funciones holonómicas.
Software para trabajar con secuencias P-recursivas y funciones generadoras holonómicas
Las herramientas para procesar y trabajar con secuencias P-recursivas en Mathematica incluyen los paquetes de software proporcionados para uso no comercial en el sitio de software de combinatoria algorítmica de RISC Combinatorics Group . A pesar de ser principalmente de código cerrado, el paquete Guess proporciona herramientas particularmente poderosas en este paquete de software 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 P-recurrencias para muchas sumas y resuelva para soluciones de forma cerrada para P-recurrencias que involucran números armónicos generalizados . [16] Otros paquetes enumerados en este sitio RISC en particular están destinados a trabajar específicamente con funciones de generación holonómica . ( Dependiendo de la profundidad con la que este artículo aborde el tema, hay muchos, muchos otros ejemplos de herramientas de software útiles que se pueden enumerar aquí o en esta página en otra sección ) .
Relación con la transformada de Fourier de tiempo discreto
Cuando la serie converge absolutamente ,
es la transformada de Fourier en tiempo discreto de la secuencia a 0 , a 1 ,….
Crecimiento asintótico de una secuencia
En cálculo, a menudo se puede utilizar la tasa de crecimiento de los coeficientes de una serie de potencias para deducir un radio de convergencia para 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
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 completo ), y donde B ( r ) ≠ 0 entonces
utilizando la función Gamma , un coeficiente binomial o un coeficiente de conjuntos múltiples .
A menudo, este enfoque puede repetirse para generar varios términos en una serie asintótica para una n . En particular,
El crecimiento asintótico de los coeficientes de esta función de generación a continuación, se puede buscar a través de la constatación de A , B , α , β , y r para describir la función de generación, como arriba.
Un análisis asintótico similar es posible para funciones generadoras exponenciales. Con una función de generación exponencial, ¡es un n / n ! que crece según estas fórmulas asintóticas.
Crecimiento asintótico de la secuencia de cuadrados
Como se derivó anteriormente, la función generadora ordinaria para la secuencia de cuadrados es
Con r = 1, α = −1, β = 3, A ( x ) = 0 y B ( x ) = x +1, podemos verificar que los cuadrados crecen como se esperaba, como los cuadrados:
Crecimiento asintótico de los números catalanes
La función generadora ordinaria para los números catalanes es
Con r = 1/4, α = 1, β = −1/2, A ( x ) = 1/2 y B ( x ) = −1/2, podemos concluir que, para los números catalanes,
Funciones generadoras bivariadas y multivariadas
Se pueden definir funciones generadoras en varias variables para matrices con varios índices. Estas se denominan funciones generadoras multivariadas o, a veces, funciones supergeneradoras . Para dos variables, a menudo se les llama funciones generadoras bivariadas .
Por ejemplo, desde es la función generadora ordinaria de coeficientes binomiales para un n fijo , se puede solicitar una función generadora bivariada que genere los coeficientes binomialespara todos los k y n . Para hacer esto, considerecomo una secuencia en sí misma, en n , y encuentre la función generadora en y que tiene estos valores de secuencia como coeficientes. Dado que la función generadora de es
la función generadora de los coeficientes binomiales es:
Representación por fracciones continuas (fracciones J de tipo Jacobi)
Definiciones
Ampliaciones de (formal) Jacobi de tipo y Stieltjes de tipo continuaron fracciones ( J-fracciones y S-fracciones , respectivamente) cuya los convergentes racionales representan 2 h {\ Displaystyle 2h}
Las series de potencias precisas de orden son otra forma de expresar las funciones generadoras ordinarias típicamente divergentes para muchas secuencias especiales de una y dos variantes. 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 potencia correspondientes con respecto a para algunas secuencias de componentes específicas dependientes de la aplicación, y , dónde denota la variable formal en la expansión de la segunda serie de potencias que se indica a continuación: [17]
Los coeficientes de , denotado en forma abreviada por , en las ecuaciones anteriores corresponden a soluciones matriciales de las ecuaciones
dónde , por , Si y donde para todos los enteros , tenemos una relación de fórmula de adición dada por
Propiedades de las h- ésimas funciones convergentes
Para (aunque en la práctica cuando ), podemos definir lo racional convergentes a la fracción J infinita, , expandido por
componentes a través de las secuencias, y , definido recursivamente por
Además, la racionalidad de la función convergente, para todos implica ecuaciones en diferencias finitas adicionales y propiedades de congruencia satisfechas por la secuencia de , Y para Si entonces tenemos la congruencia
para elecciones determinadas no simbólicas de las secuencias de parámetros, y , Cuándo , es decir, cuando estas secuencias no dependen implícitamente de un parámetro auxiliar como , , o como en los ejemplos contenidos en la tabla siguiente.
Ejemplos de
La siguiente tabla proporciona ejemplos de fórmulas de forma cerrada para las secuencias componentes que se encuentran computacionalmente (y que posteriormente se probaron correctas en las referencias citadas [18] ) en varios casos especiales de las secuencias prescritas, generado por las expansiones generales de las fracciones J definidas en la primera subsección. Aquí definimos y los parámetros , y ser indeterminadas con respecto a estas expansiones, donde las secuencias prescritas enumeradas por las expansiones de estas fracciones J se definen en términos del símbolo q-Pochhammer , el símbolo de Pochhammer y los coeficientes binomiales .
Los radios de convergencia de estas series correspondientes a la definición de las fracciones J de tipo Jacobi dadas anteriormente son en general diferentes de los de las correspondientes expansiones de series de potencia que definen las funciones generadoras ordinarias de estas secuencias.
Ejemplos de
Las funciones generadoras para la secuencia de números cuadrados a n = n 2 son:
Función de generación ordinaria
Función generadora exponencial
Serie Lambert
Como ejemplo de una identidad de serie de Lambert que no se da en el artículo principal , podemos mostrar que paratenemos eso [19]
donde tenemos la identidad de caso especial para la función generadora de la función divisor ,, dada por
Serie campana
Función de generación de la serie de Dirichlet
utilizando la función zeta de Riemann .
La secuencia a k generada por una función generadora de series de Dirichlet (DGF) correspondiente a:
dónde es la función zeta de Riemann , tiene la función generadora ordinaria:
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 y las sumas de las columnas son . Entonces, según IJ Good , [20] el número de tales tablas es el coeficiente de
en
En el caso bivariado, ejemplos no polinomiales de doble suma de las llamadas funciones " dobles " o " super " generadoras de la formaincluyen las siguientes funciones generadoras de dos variables para los coeficientes binomiales , los números de Stirling y los números eulerianos : [21]
Aplicaciones
Varias técnicas: evaluar sumas y abordar otros problemas con la generación de funciones
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 . Entonces sabemos que para las funciones generadoras ordinarias correspondientes.
Por ejemplo, podemos manipular , dónde son los números armónicos . Dejarser la función generadora ordinaria de los números armónicos. Luego
y por lo tanto
Utilizando , convolución con el numerador produce
que también se puede escribir como
Ejemplo 2: Sumas de coeficientes binomiales modificadas y la transformada binomial
Como otro ejemplo del uso de funciones generadoras para relacionar secuencias y manipular sumas, para una secuencia arbitraria definimos las dos secuencias de sumas
para todos y tratar de expresar las segundas sumas en términos de las primeras. Sugerimos un enfoque generando funciones.
Primero, usamos la transformada binomial para escribir la función generadora para la primera suma como
Dado que la función generadora de la secuencia es dado por , podemos escribir la función generadora para la segunda suma definida anteriormente en la forma
En particular, podemos escribir esta función de generación de suma modificada en forma de
por , , , y dónde .
Finalmente, se deduce que podemos expresar las segundas sumas a través de las primeras sumas de la siguiente forma:
Ejemplo 3: generación de funciones para secuencias recursivas entre sí
En este ejemplo, reformulamos un ejemplo de función generadora que se da 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) para enlosar un rectángulo sin marcar piezas de dominó. Deje que la secuencia auxiliar,, definirse como el número de formas de cubrir un rectángulo-menos-esquina sección del rectángulo completo. Buscamos utilizar estas definiciones para dar una fórmula de forma cerrada parasin desglosar más esta definición para manejar los casos de dominó vertical versus horizontal. Observe que las funciones generadoras ordinarias para nuestras dos secuencias corresponden a la serie
Si consideramos las posibles configuraciones que se pueden dar partiendo del borde izquierdo del rectángulo, podemos expresar las siguientes relaciones de recurrencia mutuamente dependientes o recursivas para nuestras dos secuencias cuando definido como arriba donde , , , y :
Ya que tenemos eso para todos los enteros , las funciones generadoras de índice desplazado satisfacen (por cierto, también tenemos una fórmula correspondiente cuando dada por ), 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
que luego implica al resolver el sistema de ecuaciones (y este es el truco particular de nuestro método aquí) que
Por lo tanto, al realizar simplificaciones algebraicas a la secuencia resultante de las segundas expansiones de fracciones parciales de la función generadora en la ecuación anterior, encontramos que y eso
para todos los enteros . 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 del uso de funciones generadoras para resolver relaciones de recurrencia en una variable ya cubierta, o al menos insinuada, en la subsección sobre racional funciones dadas anteriormente.
Convolución (productos Cauchy)
Una convolución discreta de los términos en dos series formales de potencia 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 ).
Considere que A ( z ) y B ( z ) son funciones generadoras ordinarias.
Considere que A ( z ) y B ( z ) son funciones generadoras exponenciales.
Considere la secuencia triplemente convolucionada resultante del producto de tres funciones generadoras ordinarias
Considera el -pliegue de convolución de una secuencia consigo misma para algún entero positivo (vea el ejemplo a continuación para ver una aplicación)
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 se denota por , entonces podemos mostrar que para dos variables aleatorias cualesquiera [22]
Si y son independientes. Del mismo modo, la cantidad de formas de pago centavos en denominaciones de monedas de valores en el conjunto (es decir, en centavos, cinco centavos, diez centavos, veinticinco centavos y medio dólar, respectivamente) es generado por el producto
y además, si permitimos la centavos a pagar en monedas de cualquier denominación entera positiva, llegamos a la generación del número de tales combinaciones de cambio generadas por la función de partición que genera la función expandida por el símbolo infinito q-Pochhammer producto de.
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 ,. En particular, esta secuencia tiene la interpretación combinatoria como el número de formas de insertar paréntesis en el productode modo que el orden de multiplicación esté completamente especificado. Por ejemplo, que corresponde a las dos expresiones y . 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, , satisfactorio
Desde , luego llegamos a una fórmula para esta función generadora dada por
Tenga en cuenta que la primera ecuación que define implícitamente arriba implica que
lo que luego conduce a otra expansión fraccional continua "simple" (como en forma) de esta función generadora.
Ejemplo: árboles de expansión de abanicos y convoluciones de convoluciones
Un fan del orden se define como un gráfico en los vértices con aristas conectadas de acuerdo con las siguientes reglas: Vértice está conectado por un solo borde entre sí vértices y vértice está conectado por un solo borde al siguiente vértice para todos . [23] Hay un ventilador de orden uno, tres ventiladores de orden dos, ocho ventiladores de orden tres, y así sucesivamente. Un árbol de expansión es un subgrafo de un gráfico que contiene todos los vértices originales y que contiene suficientes aristas para conectar este subgrafo, pero no tantos como para que haya un ciclo en el subgrafo. Preguntamos cuántos árboles de expansión de un fan del orden son posibles para cada .
Como observación, podemos abordar la cuestión contando el número de formas de unir conjuntos de vértices adyacentes. Por ejemplo, cuando, tenemos eso , que es una suma sobre el -pliegues de las convoluciones de la secuencia por . De manera más general, podemos escribir una fórmula para esta secuencia como
de lo cual vemos que la función generadora ordinaria para esta secuencia viene dada por la siguiente suma de convoluciones como
de la cual podemos extraer una fórmula exacta para la secuencia tomando la expansión de fracción parcial de la última función generadora.
Funciones generadoras implícitas y fórmula de inversión de Lagrange
Introduciendo un parámetro gratuito (método de aceite de serpiente)
A veces la suma es complicado y no siempre es fácil de evaluar. El método del "parámetro libre" es otro método (llamado "aceite de serpiente" por H. Wilf) para evaluar estas sumas.
Ambos métodos discutidos hasta ahora tienen como límite en la suma. Cuando n no aparece explícitamente en la suma, podemos considerar como un parámetro "gratuito" y tratar como un coeficiente de , cambia el orden de las sumas en y e intente calcular la suma interna.
Por ejemplo, si queremos calcular
podemos tratar como un parámetro "gratuito" y establecer
La suma intercambiable ("aceite de serpiente") da
Ahora la suma interna es . Por lo tanto
Entonces obtenemos
Las funciones generadoras demuestran congruencias
Decimos que dos funciones generadoras (series de potencias) son congruentes módulo , escrito si sus coeficientes son congruentes módulo para todos , es decir, para todos los casos relevantes de los enteros (tenga en cuenta que no necesitamos suponer que es un número entero aquí, es muy posible que tenga un valor polinomial en alguna forma indeterminada , por ejemplo). Si la función de generación del lado derecho " más simple ",, es una función racional de , entonces la forma de esta secuencia sugiere que la secuencia es eventualmente periódica modulo fijo casos particulares de valores enteros. Por ejemplo, podemos probar que los números de Euler ,, satisfaga el siguiente módulo de congruencia : [24]
Uno de los métodos más útiles, si no francamente poderosos, de obtener congruencias para secuencias enumeradas por funciones generadoras especiales módulo cualquier número entero (es decir, no solo potencias primas) se da en la sección sobre representaciones de fracciones continuas de funciones generadoras ordinarias (incluso no convergentes) por fracciones J arriba. Citamos un resultado particular relacionado con la generación de series expandidas a través de una representación por fracción continua de las Conferencias de Lando sobre funciones generadoras de la siguiente manera:
Teorema: (Congruencias para series generadas por expansiones de fracciones continuas) Suponga que la función generadora está representado por una fracción continua infinita de la forma
y eso denota el convergente a esta expansión de fracción continua definida de tal manera que para todos . Entonces 1) la función es racional para todos donde asumimos que uno de los criterios de divisibilidad de se cumple, es decir, para algunos ; y 2) Si el entero divide el producto , entonces tenemos eso .
Las funciones generadoras también tienen otros usos para probar congruencias para 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 (matemáticas) que muestran la versatilidad de generar funciones para abordar problemas que involucran secuencias enteras .
Los números de Stirling modulo pequeños enteros
El artículo principal sobre los números de Stirling generados por los productos finitos
proporciona una descripción general de las congruencias de estos números derivados estrictamente de las propiedades de su función generadora, como se muestra en la Sección 4.6 de la función Generadora de referencia común de Wilf . Repetimos el argumento básico y notamos que cuando reduce módulo, estas funciones de generación de productos finitos satisfacen cada una
lo que implica que la paridad de estos números de Stirling coincide con la del coeficiente binomial
y en consecuencia muestra que es incluso cuando .
De manera similar, podemos reducir los productos del lado derecho que definen el módulo de funciones generadoras de números de Stirling para obtener expresiones un poco más complicadas siempre que
Congruencias para la función de partición
En este ejemplo, extraemos parte de la maquinaria de productos infinitos cuyas expansiones de series de potencia generan las expansiones de muchas funciones especiales y enumeramos funciones de partición. En particular, recordamos que la función de partición es generado por el producto de símbolo q-Pochhammer infinito recíproco (o producto z-Pochhammer según sea el caso) dado por
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 congruencias enteras relacionadas para la función: [25]
Mostramos cómo usar 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.
Primero, observamos que la función generadora del coeficiente binomial, , satisface que cada uno de sus coeficientes sea divisible por con excepción de las que corresponden a las competencias de , todos los cuales, de lo contrario, tienen un resto de modulo . Así podemos escribir
que en particular nos muestra que
Por lo tanto, vemos fácilmente que divide cada coeficiente de en las infinitas expansiones de productos de
Finalmente, dado que podemos escribir la función generadora para la función de partición como
podemos equiparar los coeficientes de en las ecuaciones anteriores para probar nuestro resultado de congruencia deseado, es decir, que, para todos .
Transformaciones de funciones generadoras
Hay una serie de transformaciones de funciones generadoras que proporcionan otras aplicaciones (consulte el artículo principal ). Una transformación de la función generadora ordinaria (OGF) de una secuencia proporciona un método para convertir la función generadora de una secuencia en una función generadora que enumera otra. Estas transformaciones generalmente involucran fórmulas integrales que involucran una secuencia OGF (ver transformaciones integrales ) o sumas ponderadas sobre las derivadas de orden superior de estas funciones (ver transformaciones derivadas ).
Las transformaciones de funciones generadoras pueden entrar en juego cuando buscamos expresar una función generadora para las sumas
en forma de que involucra la función generadora de secuencia original. Por ejemplo, si las sumas, entonces la función generadora de las expresiones de suma modificadas viene dada por [26] (ver también la transformada binomial y la transformada de Stirling ).
ejercicio 5.71
También hay fórmulas integrales para convertir entre el OGF de una secuencia, , y su función de generación exponencial, o EGF, , y viceversa dado por
siempre que estas integrales converjan para valores apropiados de .
Otras aplicaciones
Las funciones generadoras se utilizan para:
Encuentre una fórmula cerrada para una secuencia dada en una relación de recurrencia. Por ejemplo, considere los números de Fibonacci .
Encuentre relaciones de recurrencia para secuencias: la forma de una función generadora puede sugerir una fórmula de recurrencia.
Encuentre relaciones entre secuencias: si las funciones generadoras de dos secuencias tienen una forma similar, entonces las secuencias mismas pueden estar relacionadas.
Explore el comportamiento asintótico de las secuencias.
Demuestre identidades que involucren secuencias.
Resolver problemas de enumeración en combinatoria y codificar sus soluciones. Los polinomios de torre son un ejemplo de una aplicación en combinatoria.
Evalúa sumas infinitas.
Otras funciones generadoras
Ejemplos de
Ejemplos de secuencias polinómicas generadas por funciones generadoras más complejas incluyen:
Polinomios de Appell
Polinomios de Chebyshev
Polinomios de diferencia
Polinomios de Appell generalizados
Polinomios de diferencia Q
Otras secuencias generadas por funciones generadoras más complejas:
Funciones generadoras exponenciales dobles. Por ejemplo: Aitken's Array: Triangle of Numbers
Productos de Hadamard de funciones generadoras / funciones generadoras diagonales y sus correspondientes transformaciones integrales
Polinomios de convolución
El artículo de Knuth titulado " Polinomios de convolución " [27] define una clase generalizada de secuencias polinomiales de convolución por sus funciones generadoras especiales de la forma
para alguna función analítica con una expansión en serie de potencia tal que . Decimos que una familia de polinomios,, forma una familia de convolución si y si la siguiente condición de convolución se cumple para todos y para todos :
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 es de tipo binomial
Los valores especiales de la secuencia incluyen y , y
Por arbitrario (fijo) , estos polinomios satisfacen fórmulas de convolución de la forma
Para un parámetro fijo distinto de cero , hemos modificado las funciones generadoras para estas secuencias polinomiales de convolución dadas por
dónde está implícitamente definido por una ecuación funcional de la forma. Además, podemos usar métodos matriciales (como en la referencia) para demostrar que dadas dos secuencias polinómicas de convolución, y , con las respectivas funciones de generación correspondientes, y , luego por arbitrario tenemos la identidad
Ejemplos de secuencias polinomiales de convolución incluyen la serie de potencia binomial ,, los llamados polinomios de árboles , los números de Bell ,, 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 la función de generación de Wilf se encuentran varias funciones generadoras de secuencias especiales y útiles . Otras funciones de generación especiales de nota incluyen las entradas en la siguiente tabla, que de ninguna manera está completa. [28]
Serie de poder formal
Fórmula de función generadora
Notas
es un número armónico de primer orden
es un número de Bernoulli
es un número de Fibonacci y
denota el factorial ascendente , o símbolo Pochhammer y algún número entero
es la función polilogaritmo yes un número armónico generalizado para
es un número de Stirling del segundo tipo y donde los términos individuales en la expansión satisfacen
El caso de dos variables viene dado por
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 usó el dispositivo de generar funciones mucho antes que Laplace [..]. Aplicó esta herramienta matemática a varios problemas en Análisis Combinatorio y Teoría de Números .
Ver también
Función generadora de momentos
Función generadora de probabilidad
Generando transformación de función
Teorema de reciprocidad de Stanley
Aplicaciones a la partición (teoría de números)
Principios combinatorios
Tamizado cíclico
Transformada Z
Notas
^ Knuth, Donald E. (1997). "§1.2.9 Generar funciones". Algoritmos fundamentales . El arte de la programación informática . 1 (3ª ed.). Addison-Wesley. ISBN 0-201-89683-4.
^ Este término alternativo ya se puede encontrar en EN Gilbert (1956), "Enumeración de gráficos etiquetados", Canadian Journal of Mathematics 3, p. 405–411 , pero su uso es raro antes del año 2000; desde entonces parece estar aumentando.
^ Flajolet y Sedgewick 2009 , p. 95
^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 0.335,10001 págs. 42–43
^ Wilf 1994 , p. 56
^ Wilf 1994 , p. 59
^Hardy, GH; Wright, EM; Heath-Brown, DR; Silverman, JH (2008). Introducción a la teoría de los números (6ª ed.). Prensa de la Universidad de Oxford. pag. 339 . ISBN 9780199219858.Mantenimiento CS1: fecha y año ( enlace )
^Spivey, Michael Z. (2007). "Sumas combinatorias y diferencias finitas". Matemáticas discretas . 307 (24): 3130–3146. doi : 10.1016 / j.disc.2007.03.052 . Señor 2370116 .
^Mathar, RJ (2012). "Otra tabla más de integrales". arXiv : 1207.5845 [ matemáticas.CA ].v4 eq. (0,4)
^ Graham, Knuth & Patashnik 1994 , Tabla 265 en §6.1 para identidades de suma finita que involucran los triángulos numéricos de Stirling.
^ Lando 2003 , §2.4
^ Ejemplo de Stanley, Richard P .; Fomin, Sergey (1997). "§6.3". Combinatoria enumerativa: Volumen 2 . Estudios de Cambridge en Matemáticas Avanzadas. 62 . Prensa de la Universidad de Cambridge. ISBN 978-0-521-78987-5.
^ Knuth 1997 , §1.2.9
^ Solución a Graham, Knuth & Patashnik 1994 , p. 569, ejercicio 7.36
^ Flajolet y Sedgewick 2009 , §B.4
^Schneider, C. (2007). "La suma simbólica ayuda a la combinatoria" . Sem. Lothar. Combin . 56 : 1–36.
^ Para obtener información más completa sobre las propiedades de las fracciones J, consulte:
Flajolet, P. (1980). "Aspectos combinatorios de fracciones continuas" (PDF) . Matemáticas discretas . 32 (2): 125-161. doi : 10.1016 / 0012-365X (80) 90050-3 .
Wall, SA (2018) [1948]. Teoría analítica de fracciones continuas . Dover. ISBN 978-0-486-83044-5.
^ Consulte los siguientes artículos:
Schmidt, Maxie D. (2016). "Continuación de fracciones para funciones generadoras de series cuadradas". arXiv : 1612.02778 .
- (2017). "Fracciones continuas de tipo Jacobi para las funciones generadoras ordinarias de funciones factoriales generalizadas" . Diario de secuencias de enteros . 20 . 17.3.4.
- (2017). "Fracciones continuas tipo Jacobi y congruencias para coeficientes binomiales Modulo Enteros". arXiv : 1702.01374 .
^"Identidad de la serie Lambert" . Desbordamiento matemático . 2017.
^Bueno, IJ (1986). "Sobre aplicaciones de distribuciones de Dirichlet simétricas y sus mezclas a tablas de contingencia" . Annals of Statistics . 4 (6): 1159-1189. doi : 10.1214 / aos / 1176343649 .
^ Consulte el uso de estos términos en Graham, Knuth & Patashnik 1994 , §7.4 sobre funciones generadoras de secuencias especiales.
^ Graham, Knuth y Patashnik 1994 , §8.3
^ Graham, Knuth & Patashnik 1994 , Ejemplo 6 en §7.3 para otro método y la configuración completa de este problema usando funciones generadoras. Esteenfoquemás " complicado " se da en la Sección 7.5 de la misma referencia.
^ Lando 2003 , §5
^ Hardy y col. 2008 , §19.12
^ Graham, Knuth y Patashnik 1994 , p. 535, ejercicio 5.71
^ Consulte también las funciones generadoras 1031 que se encuentran en Plouffe, Simon (1992). Approximations de séries génératrices et quelques conjectures [ Aproximaciones de funciones generadoras y algunas conjeturas ] (Maestría) (en francés). Université du Québec à Montréal. arXiv : 0911.4975 .
Referencias
Aigner, Martin (2007). Un curso de enumeración . Textos de Posgrado en Matemáticas. 238 . Saltador. 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 función generadora" . Actas del Sexto Simposio de Berkeley sobre Probabilidad y Estadística Matemática . 2 : 267–318. Zbl 0267.05002 . Reimpreso en Rota, Gian-Carlo (1975). "3. La idea de generar función". Cálculo de operadores finitos . Con la colaboración de P. Doubilet, C. Greene, D. Kahaner, A. Odlyzko y R. Stanley . Prensa académica. págs. 83-134. ISBN 0-12-596650-4. Zbl 0328.05007 .
Flajolet, Philippe ; Sedgewick, Robert (2009). Combinatoria analítica . Prensa de la Universidad de Cambridge. ISBN 978-0-521-89806-5. Zbl 1165.05001 .
Goulden, Ian P .; Jackson, David M. (2004). Enumeración combinatoria . Publicaciones de Dover . ISBN 978-0486435978.
Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). "Capítulo 7: Generación de funciones". Matemáticas concretas. Una base para la informática (2ª ed.). Addison-Wesley. págs. 320–380. ISBN 0-201-55802-5. Zbl 0836.00001 .
Lando, Sergei K. (2003). Conferencias sobre generación de funciones . Sociedad Matemática Estadounidense. ISBN 978-0-8218-3481-7.
Wilf, Herbert S. (1994). Generatingfunctionology (2ª ed.). Prensa académica. ISBN 0-12-751956-4. Zbl 0831.05001 .
enlaces externos
"Introducción a las funciones generadoras ordinarias" por Mike Zabrocki, Universidad de York, Matemáticas y Estadística