Funciones Generatrices Exponenciales

Teoría

Las Funciones Generatrices Exponenciales (FGE) son una herramienta súper potente en combinatoria, diseñadas específicamente para contar estructuras etiquetadas. Mientras que las Funciones Generatrices Ordinarias (FGO) se usan normalmente para objetos no etiquetados (como partir un entero o repartir pelotas idénticas), las FGE se usan cuando importa que los elementos sean distintos (como formar palabras, permutaciones o grafos etiquetados). La FGE para una sucesión ${a_n}{n \ge 0}$ es la serie de potencias formal $A(x) = \sum{n=0}^{\infty} a_n \frac{x^n}{n!}$. Que incluyamos el $n!$ en el denominador no es algo arbitrario; sirve para compensar las permutaciones de las $n$ etiquetas distintas.

El poder principal de las FGE está en cómo manejan la combinación de estructuras. Cuando multiplicas dos FGE, los coeficientes resultantes generan automáticamente coeficientes binomiales. Esto corresponde a la acción combinatoria de partir un conjunto de $n$ etiquetas distintas en dos subconjuntos, asignando una estructura de tipo $A$ al primer subconjunto y una de tipo $B$ al segundo. Esta "Fórmula del Producto" permite que descompongas problemas combinatorios complejos en productos o composiciones de funciones más simples.

Por ejemplo, si quieres contar de cuántas formas puedes formar una estructura que consiste en una colección de subestructuras ajenas (como una permutación que es una colección de ciclos ajenos, o un grafo que es una colección de componentes conexas), puedes usar seguido la fórmula exponencial. Si $A(x)$ describe las componentes conexas, entonces $e^{A(x)}$ describe la colección de esas componentes. Esta traducción algebraica de la descomposición estructural hace que las FGE sean indispensables para problemas que involucran desajustes (derangements), números de Stirling y árboles etiquetados (Fórmula de Cayley).

Fórmulas Clave

Definición La Función Generatriz Exponencial para una sucesión ${a_n}{n \ge 0}$ es: $$A(x) = \sum{n=0}^{\infty} a_n \frac{x^n}{n!}$$

La Fórmula del Producto (Convolución Binomial) Si $A(x)$ es la FGE para ${a_n}$ y $B(x)$ es la FGE para ${b_n}$, entonces su producto $C(x) = A(x)B(x)$ es la FGE para la sucesión ${c_n}$, donde: $$c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$$ Combinatoriamente, $c_n$ cuenta el número de formas de partir un conjunto de tamaño $n$ en dos subconjuntos de tamaño $k$ y $n-k$, formando una estructura de tipo $A$ en el primero y de tipo $B$ en el segundo.

La Fórmula Exponencial (Composición) Si $A(x)$ es la FGE para un conjunto de estructuras etiquetadas conexas (con $a_0=0$), entonces la FGE para colecciones de componentes ajenas de estas estructuras es: $$H(x) = e^{A(x)} = \sum_{k=0}^\infty \frac{A(x)^k}{k!}$$ Aquí, el coeficiente de $\frac{x^n}{n!}$ en $H(x)$ cuenta de cuántas formas puedes partir ${1, \dots, n}$ en subconjuntos no vacíos y construir una estructura de tipo $A$ en cada subconjunto.

FGE Elementales Comunes

• Permutaciones ($a_n = n!$): $$\sum_{n=0}^{\infty} n! \frac{x^n}{n!} = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$$
• Todos los subconjuntos / Estructura arbitraria ($a_n = 1$): $$\sum_{n=0}^{\infty} 1 \cdot \frac{x^n}{n!} = e^x$$
• Permutaciones circulares / Ciclos ($a_n = (n-1)!$ para $n \ge 1$): $$\sum_{n=1}^{\infty} (n-1)! \frac{x^n}{n!} = \sum_{n=1}^{\infty} \frac{x^n}{n} = \ln\left(\frac{1}{1-x}\right)$$

Demostración

Teorema: La Fórmula del Producto Sean $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ y $B(x) = \sum_{n=0}^{\infty} b_n \frac{x^n}{n!}$. Sea $C(x) = A(x)B(x)$. Si escribes $C(x) = \sum_{n=0}^{\infty} c_n \frac{x^n}{n!}$, entonces $c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$.

Demostración: Empieza multiplicando las dos series infinitas $A(x)$ y $B(x)$ usando la regla estándar del producto de Cauchy para series de potencias. $$C(x) = A(x)B(x) = \left( \sum_{i=0}^{\infty} \frac{a_i}{i!} x^i \right) \left( \sum_{j=0}^{\infty} \frac{b_j}{j!} x^j \right)$$

Para encontrar el término que tiene $x^n$ en el producto, suma sobre todos los pares $(i, j)$ tales que $i + j = n$. Toma $k = i$, así que $j = n - k$. El coeficiente de $x^n$ en la expansión de $C(x)$ es: $$[x^n]C(x) = \sum_{k=0}^n \left( \frac{a_k}{k!} \cdot \frac{b_{n-k}}{(n-k)!} \right)$$

Por la definición de la FGE $C(x)$, el coeficiente de $x^n$ es explícitamente $\frac{c_n}{n!}$. Por lo tanto, iguala los coeficientes: $$\frac{c_n}{n!} = \sum_{k=0}^n \frac{a_k b_{n-k}}{k!(n-k)!}$$

Para despejar $c_n$, multiplica ambos lados de la ecuación por $n!$: $$c_n = n! \sum_{k=0}^n \frac{a_k b_{n-k}}{k!(n-k)!} = \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k}$$

Aquí puedes reconocer el coeficiente binomial $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. Al sustituir esto en la suma, obtienes: $$c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$$ $\square$