Armando EGFs

Teoría

Las Funciones Generatrices Exponenciales (EGFs) son la herramienta algebraica principal que se usa para contar estructuras combinatorias etiquetadas. Mientras que las Funciones Generatrices Ordinarias (OGFs) usan coeficientes de $x^n$ para contar objetos sin etiquetas, las EGFs usan los coeficientes de $\frac{x^n}{n!}$. Específicamente, para una sucesión de números ${a_n}{n \ge 0}$ que representa el número de formas de construir una estructura en un conjunto de $n$ etiquetas distintas (normalmente ${1, 2, \dots, n}$), la función generatriz exponencial la definimos como $A(x) = \sum{n=0}^{\infty} a_n \frac{x^n}{n!}$.

El poder de las EGFs reside en cómo manejan la distribución de etiquetas durante las operaciones combinatorias. Cuando combinas dos estructuras etiquetadas, tienes que decidir no solo qué estructuras elegir, sino también cómo repartir las etiquetas disponibles entre ellas. El factor de $\frac{1}{n!}$ en el denominador funciona en perfecta armonía con el teorema del binomio. Por consecuencia, al multiplicar dos EGFs, automáticamente tomas en cuenta el coeficiente binomial $\binom{n}{k}$, que representa el número de formas de elegir etiquetas para las subestructuras.

Esta técnica es indispensable en las matemáticas de olimpiada para problemas que involucran permutaciones, gráficas etiquetadas, particiones de conjuntos y números de Stirling. La intuición fundamental es que si tienes una estructura compuesta por componentes independientes $A$ y $B$, la EGF para la estructura combinada es simplemente el producto $A(x)B(x)$. Esto permite que relaciones de recurrencia complejas que involucran coeficientes binomiales se puedan resolver traduciéndolas a ecuaciones diferenciales o ecuaciones funcionales en términos de $A(x)$.

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 Fundamental (Convolución Binomial) Si $A(x)$ genera a ${a_n}$ y $B(x)$ genera a ${b_n}$, entonces el producto $C(x) = A(x)B(x)$ genera la sucesión ${c_n}$ dada por: $$c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$$ Combinatoriamente, $c_n$ cuenta el número de formas de dividir un conjunto de $n$ etiquetas en dos conjuntos de tamaño $k$ y $n-k$, construir una estructura de tipo $A$ en el primer conjunto y una estructura de tipo $B$ en el segundo.

La Fórmula Exponencial (Composición) Si $A(x)$ es la EGF para una estructura etiquetada conexa (con $a_0=0$), entonces $e^{A(x)}$ es la EGF para colecciones de componentes disjuntos de esa estructura: $$\text{Si } H(x) = e^{A(x)}, \text{ entonces } h_n \text{ cuenta conjuntos de componentes de tipo } A \text{ sobre } n \text{ etiquetas.}$$

EGFs 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 mapeos $f: {1..n} \to {1..n}$ ($a_n = n^n$): $\sum_{n=0}^\infty n^n \frac{x^n}{n!}$
• Conjuntos de un solo elemento ($a_1=1$, los demás 0): $x$
• Conjunto vacío ($a_0=1$, los demás 0): $1$
• Sucesión uniforme ($a_n = 1$): $e^x$

Demostración

Teorema: La Fórmula del Producto para EGFs

Lo que hay que demostrar es que si $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!}$, entonces el coeficiente de $\frac{x^n}{n!}$ en el producto $A(x)B(x)$ es $c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}$.

Demostración:

1. Escribe el producto de las dos series usando la regla del producto de Cauchy para series de potencias. $$ 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) $$

2. Para encontrar el coeficiente de $x^n$ en el producto, suma sobre todos los pares $(i, j)$ tales que $i + j = n$. Toma $k = i$, de modo que $j = n - k$. $$ x^n = \sum_{k=0}^n \left( \frac{a_k}{k!} \cdot \frac{b_{n-k}}{(n-k)!} \right) $$

3. Lo que quieres es expresar esto en la forma de un coeficiente de EGF, que es $[x^n/n!] = n! [x^n]$. Por lo tanto, multiplica el coeficiente de $x^n$ por $n!$ para encontrar $c_n$: $$ c_n = n! \sum_{k=0}^n \frac{a_k}{k!} \frac{b_{n-k}}{(n-k)!} $$

4. Mete el $n!$ dentro de la sumatoria: $$ c_n = \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} $$

5. Reconoce la definición del coeficiente binomial $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. Al sustituir esto de nuevo en la suma, obtienes: $$ c_n = \sum_{k=0}^n \binom{n}{k} a_k b_{n-k} $$

Así, $A(x)B(x)$ es la función generatriz exponencial para la sucesión ${c_n}$.

$\square$