Funciones Generatrices Ordinarias

Teoría

Las Funciones Generatrices Ordinarias (FGO) son un puente muy poderoso entre la combinatoria discreta y el análisis o álgebra continua. Una FGO transforma una sucesión de números $(a_0, a_1, a_2, \dots)$ en una serie de potencias formal $A(x) = \sum_{n=0}^{\infty} a_n x^n$. En este contexto, la variable $x$ no suele ser un número específico que quieras evaluar, sino más bien un "marcador" o una "etiqueta" que mantiene los coeficientes en orden. Como Herbert Wilf describió de forma famosa, una función generatriz es un tendedero donde cuelgas una sucesión de números para que se vean bien.

Esta técnica es fundamental en las matemáticas de competencia porque te permite manipular sucesiones combinatorias complejas usando operaciones algebraicas estándar. Las FGO son especialmente útiles para resolver relaciones de recurrencia lineales (como la sucesión de Fibonacci), analizar particiones de enteros y resolver problemas de conteo que involucran selecciones "sin orden" con repetición (selección de multiconjuntos). Al convertir una relación de recurrencia en una ecuación algebraica que involucre a $A(x)$, muchas veces puedes despejar $A(x)$ explícitamente y luego extraer los coeficientes para encontrar una fórmula cerrada para la sucesión original.

La intuición clave detrás de las FGO está en cómo se comportan los exponentes durante la multiplicación de polinomios. Como $x^a \cdot x^b = x^{a+b}$, multiplicar dos funciones generatrices corresponde a sumar los índices de sus coeficientes. Desde el punto de vista combinatorio, si $A(x)$ cuenta las formas de construir una estructura de tamaño $k$ a partir del conjunto $A$, y $B(x)$ hace lo mismo para el conjunto $B$, entonces el producto $A(x)B(x)$ cuenta las formas de formar una estructura combinada de tamaño total $n$ dividiendo $n$ en una parte de $A$ y una parte de $B$. A esto se le conoce como la convolución de sucesiones.

Fórmulas Clave

Definición Para una sucesión $a_0, a_1, a_2, \dots$, la Función Generatriz Ordinaria es: $$A(x) = \sum_{n=0}^{\infty} a_n x^n$$

Series Fundamentales La Serie Geométrica (la pieza básica más común): $$\sum_{n=0}^{\infty} x^n = 1 + x + x^2 + \dots = \frac{1}{1-x}$$

El Teorema del Binomio Generalizado (Stars and Bars / Selección de multiconjuntos): $$\sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n = \frac{1}{(1-x)^k}$$

El Teorema del Binomio (Sucesión finita): $$\sum_{k=0}^{n} \binom{n}{k} x^k = (1+x)^n$$

Operaciones Suma (Unión disjunta de conjuntos): $$A(x) + B(x) = \sum_{n=0}^{\infty} (a_n + b_n)x^n$$

Derivación (Para bajar el índice): $$x A'(x) = \sum_{n=0}^{\infty} n a_n x^n$$

La Fórmula de Convolución (Regla del Producto) Si $A(x) = \sum a_n x^n$ y $B(x) = \sum b_n x^n$, entonces su producto $C(x) = A(x)B(x)$ genera la sucesión $c_n$: $$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}$$

Demostración

Teorema: La Fórmula de Convolución Aquí se demuestra que el producto de dos funciones generatrices ordinarias corresponde a la convolución de sus sucesiones. Esto explica por qué multiplicar polinomios cuenta el número de formas de combinar dos estructuras independientes para formar una estructura de tamaño total $n$.

Demostración: Toma $A(x)$ y $B(x)$ como las funciones generatrices ordinarias para las sucesiones $(a_n)$ y $(b_n)$ respectivamente: $$A(x) = \sum_{i=0}^{\infty} a_i x^i \quad \text{y} \quad B(x) = \sum_{j=0}^{\infty} b_j x^j$$

Lo que se busca es determinar el coeficiente de $x^n$ en el producto $A(x)B(x)$. Por la definición del producto de Cauchy de series de potencias formales, multiplicas las series término a término: $$A(x)B(x) = \left( a_0 x^0 + a_1 x^1 + a_2 x^2 + \dots \right) \left( b_0 x^0 + b_1 x^1 + b_2 x^2 + \dots \right)$$

Para encontrar el término que tiene $x^n$ en este producto, tienes que considerar todos los pares posibles de términos $a_i x^i$ de la primera serie y $b_j x^j$ de la segunda serie, de tal forma que su producto contribuya a la potencia $x^n$.

El producto de dos de estos términos es: $$(a_i x^i)(b_j x^j) = a_i b_j x^{i+j}$$

Para que este término contribuya al coeficiente de $x^n$, los exponentes deben sumar $n$. Es decir, necesitas que: $$i + j = n \implies j = n - i$$

Como $i$ y $j$ tienen que ser enteros no negativos, $i$ puede ir desde $0$ hasta $n$. Para cada $i$ válido, hay exactamente un $j$ correspondiente (específicamente $n-i$). Sumas todas esas contribuciones para encontrar el coeficiente total de $x^n$, que llamaremos $c_n$:

$$c_n = a_0 b_n + a_1 b_{n-1} + a_2 b_{n-2} + \dots + a_n b_0$$

Esto lo puedes escribir de forma compacta usando la notación de sumatoria: $$c_n = \sum_{i=0}^{n} a_i b_{n-i}$$

Así, el producto de las funciones generatrices es: $$A(x)B(x) = \sum_{n=0}^{\infty} \left( \sum_{k=0}^{n} a_k b_{n-k} \right) x^n$$

Esto confirma que el coeficiente de $x^n$ en el producto $A(x)B(x)$ es, efectivamente, la convolución de las sucesiones $(a_n)$ y $(b_n)$. $\square$