Funciones Generadoras

Teoría

Las funciones generadoras son un puente muy poderoso entre la matemática discreta y el análisis continuo, y te permiten tratar sucesiones de números como si fueran coeficientes de una serie de potencias formal. La idea central es codificar una sucesión infinita $(a_0, a_1, a_2, \dots)$ en una sola función $A(x) = a_0 + a_1x + a_2x^2 + \dots$. Al transformar una sucesión en una función, puedes aplicar operaciones algebraicas —como suma, multiplicación, derivación y composición— para manipular la sucesión completa. Esta técnica se describe seguido con la analogía de Herbert Wilf: "Una función generadora es un tendedero donde colgamos una sucesión de números para exhibirlos".

En el contexto de las olimpiadas de matemáticas, las funciones generadoras se usan principalmente para resolver relaciones de recurrencia, contar particiones y manejar problemas combinatorios con restricciones específicas. Son especialmente útiles cuando quieres "combinar" estructuras. Por ejemplo, si tienes dos conjuntos de objetos y quieres contar de cuántas formas puedes formar una estructura combinada de tamaño $n$, esto corresponde algebraicamente a multiplicar sus funciones generadoras correspondientes. El coeficiente del producto resultante te da la respuesta, transformando argumentos de conteo complejos en álgebra de polinomios.

Hay dos tipos principales que te vas a encontrar en las competencias: Funciones Generadoras Ordinarias (FGO), que se usan para problemas de selección donde el orden no importa (como particiones o combinaciones), y Funciones Generadoras Exponenciales (FGE), que se usan para problemas de ordenamiento donde el orden sí importa (como permutaciones). Un punto clave al usar estas herramientas es que las tratamos como series de potencias formales; por lo general ignoramos los temas de convergencia y dominio, y nos enfocamos totalmente en la estructura algebraica de los coeficientes.

Fórmulas Clave

1. Definiciones

• Función Generadora Ordinaria (FGO): Para una sucesión $a_n$: $$A(x) = \sum_{n=0}^{\infty} a_n x^n$$
• Función Generadora Exponencial (FGE): Para una sucesión $a_n$: $$\hat{A}(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$

2. Expansiones de Series Fundamentales

• Serie Geométrica: $$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n = 1 + x + x^2 + \dots$$
• Serie Geométrica Finita: $$\frac{1-x^{k+1}}{1-x} = 1 + x + x^2 + \dots + x^k$$
• Teorema del Binomio Generalizado: $$(1+x)^\alpha = \sum_{n=0}^{\infty} \binom{\alpha}{n} x^n$$ donde $\binom{\alpha}{n} = \frac{\alpha(\alpha-1)\dots(\alpha-n+1)}{n!}$.

3. Expansión Binomial Negativa (Separadores) Una fórmula crucial para problemas de particiones y ecuaciones lineales: $$\frac{1}{(1-x)^k} = (1-x)^{-k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n = \sum_{n=0}^{\infty} \binom{n+k-1}{n} x^n$$

4. Operaciones y Convolución

• Suma: $A(x) + B(x) \leftrightarrow a_n + b_n$
• Desplazamiento: $x A(x) \leftrightarrow (0, a_0, a_1, \dots)$
• Derivación: $A'(x) = \sum_{n=1}^{\infty} n a_n x^{n-1}$ (baja el índice)
• Producto (Convolución) para FGO: $$A(x)B(x) = \sum_{n=0}^{\infty} c_n x^n \quad \text{donde} \quad c_n = \sum_{k=0}^n a_k b_{n-k}$$
• Producto para FGE: $$\hat{A}(x)\hat{B}(x) = \sum_{n=0}^{\infty} c_n \frac{x^n}{n!} \quad \text{donde} \quad c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$$

Demostración

Teorema: La Expansión Binomial Negativa (Fórmula del Coeficiente de Multiconjunto). Para cualquier entero $k \geq 1$, el coeficiente de $x^n$ en la expansión de $(1-x)^{-k}$ es $\binom{n+k-1}{n}$.

Demostración: Vamos a abordar esto interpretando la expresión algebraica de forma combinatoria.

1. Descomposición en Series Geométricas Recuerda que $\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots$. Puedes escribir $(1-x)^{-k}$ como el producto de $k$ series geométricas idénticas: $$ (1-x)^{-k} = \left(\sum_{e_1=0}^{\infty} x^{e_1}\right) \left(\sum_{e_2=0}^{\infty} x^{e_2}\right) \dots \left(\sum_{e_k=0}^{\infty} x^{e_k}\right) $$

2. Extracción del Coeficiente Para encontrar el coeficiente de $x^n$ en este producto, tienes que elegir un término $x^{e_i}$ de cada uno de los $k$ factores de tal forma que su producto sea $x^n$. $$ x^{e_1} \cdot x^{e_2} \cdot \dots \cdot x^{e_k} = x^{e_1 + e_2 + \dots + e_k} = x^n $$ Esto implica que los exponentes deben cumplir la ecuación lineal: $$ e_1 + e_2 + \dots + e_k = n $$ donde cada $e_i \geq 0$ es un entero.

3. Interpretación Combinatoria El coeficiente de $x^n$ es exactamente el número de soluciones enteras no negativas de la ecuación $e_1 + \dots + e_k = n$. Este es un problema clásico de "Separadores" (Stars and Bars). Estás distribuyendo $n$ objetos indistinguibles (las unidades del exponente) en $k$ recipientes distinguibles (los $k$ factores del producto).

4. Aplicación de Separadores El número de soluciones de $e_1 + \dots + e_k = n$ con $e_i \geq 0$ está dado por la fórmula de combinaciones con repetición: $$ \binom{n + k - 1}{k - 1} $$ Por la simetría de los coeficientes binomiales, $\binom{N}{R} = \binom{N}{N-R}$, así que lo puedes escribir como: $$ \binom{n + k - 1}{n} $$

5. Conclusión Por lo tanto, el coeficiente de $x^n$ en la expansión de $(1-x)^{-k}$ es $\binom{n+k-1}{n}$. $$ (1-x)^{-k} = \sum_{n=0}^{\infty} \binom{n+k-1}{n} x^n $$ $\square$