¿Cuáles son algunos usos elegantes de las funciones generadoras?

Answer 1

El número de particiones de un entero, [math] p (n) [/ math], es el número de formas de escribirlo como una suma de enteros [math] 1 \ le k \ le n [/ math]. Por ejemplo, [matemáticas] p (5) = 7 [/ matemáticas] porque

[matemáticas] 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 [/ matemáticas]

son todas particiones de 5. No es difícil escribir una función generadora para [math] p (n) [/ math]: if [math] f (x) = \ sum_ {n = 0} ^ \ infty p (n ) x ^ n [/ math], entonces queremos un término [math] x ^ n [/ math] para cada partición de [math] n [/ math]. Por lo tanto,

[matemáticas] f (x) = (1 + x + x ^ 2 + \ ldots) (1 + x ^ 2 + x ^ 4 \ ldots) (1 + x ^ 3 + x ^ 6 + \ ldots) = \ prod_ {j = 1} ^ \ infty \ frac {1} {1-x ^ j}. [/ math]

Los diferentes subconjuntos de las particiones también son interesantes, y también podemos escribir fácilmente funciones generadoras para estas. Por ejemplo, ¿de cuántas maneras podemos escribir [matemáticas] n [/ matemáticas] como una suma de enteros impares? Simplemente sacaríamos los valores pares de [math] j [/ math] en el producto infinito. Equivalentemente

[matemáticas] g (x) = \ prod_ {j = 1} ^ \ infty \ frac {1} {1-x ^ {2j-1}} = \ sum_ {n = 1} ^ \ infty o (n) x ^ n, [/ matemáticas]

donde [math] o (n) [/ math] es el número de particiones de [math] n [/ math] en enteros impares. Por ejemplo, [matemáticas] o (5) = 3 [/ matemáticas]. Una pregunta un poco más difícil es la cantidad de formas de escribir [matemáticas] n [/ matemáticas] como una suma de enteros distintos . Para responder esto, reemplazamos las sumas infinitas [matemáticas] (1 + x ^ j + x ^ {2j} + \ ldots) [/ matemáticas] con los binomios simples [matemáticas] 1 + x ^ j [/ matemáticas], porque usar [math] j [/ math] más de una vez no es una opción. Así,

[matemáticas] h (x) = \ prod_ {j = 1} ^ \ infty (1 + x ^ j) = \ sum_ {n = 1} ^ \ infty d (n) x ^ n, [/ matemáticas]

donde [math] d (n) [/ math] es el número de formas de escribir [math] n [/ math] como una suma de enteros distintos. Por ejemplo, [matemáticas] d (5) = 3 [/ matemáticas].

Oh, eso es interesante, [matemáticas] d (5) = o (5) [/ matemáticas]. ¿Coincidencia? Podemos verificar fácilmente usando las funciones generadoras. Tenemos

[matemáticas] \ frac {g (x)} {h (x)} = \ prod_ {j = 1} ^ \ infty \ frac {1} {(1-x ^ {2j-1}) (1 + x ^ j)} = \ prod_ {j = 1} ^ \ infty \ frac {1-x ^ j} {(1-x ^ {2j-1}) (1-x ^ {2j})} = 1. [/ matemáticas]

Esta es una prueba indolora mediante la generación de funciones para un resultado inesperado: el número de particiones de [math] n [/ math] en enteros impares es el mismo que el número de particiones de [math] n [/ math] enteros distintos.

Answer 2

Asintóticas de funciones definidas recursivamente.

A veces, dada una fórmula recursiva [matemática] f (n) [/ matemática], se puede calcular la función generadora [matemática] F (x) = \ Sigma_ {n = 0} ^ {\ infty} f (n) x ^ n [/ matemáticas]. Al calcular sus puntos singulares (es decir, el punto más cercano a 0) donde [matemática] F (x) [/ matemática] no está definida, se puede obtener el orden de crecimiento de f (n).