Convolución de sucesiones.
El producto de dos Funciones Generatrices Ordinarias (OGF) corresponde a la convolución de sus sucesiones base. Si $A(x)$ es la función generatriz de la sucesión $(a_n)$ y $B(x)$ es la función generatriz de $(b_n)$, entonces el producto $C(x) = A(x)B(x)$ genera una sucesión $(c_n)$ donde cada término $c_n$ es la suma de los productos $a_k b_{n-k}$ para todas las $k$ válidas. Combinatoriamente, esta operación modela el proceso de dividir una estructura de tamaño $n$ en dos componentes ordenados: un primer componente de tamaño $k$ (contado por $a_k$) y un segundo componente de tamaño $n-k$ (contado por $b_{n-k}$).
Esta técnica es fundamental en la enumeración combinatoria porque te permite descomponer estructuras complejas en partes más simples e independientes. Por ejemplo, si quieres contar de cuántas formas puedes construir una estructura de peso total $n$ combinando un elemento del conjunto $\mathcal{A}$ y un elemento del conjunto $\mathcal{B}$, la función generatriz del conjunto combinado es simplemente el producto de las funciones generatrices de $\mathcal{A}$ y $\mathcal{B}$. Este principio se extiende a potencias de funciones generatrices, lo que te permite resolver problemas de particiones, composiciones y distribuciones de elementos distintos en cajas idénticas.
Una aplicación específica y muy poderosa del producto de OGF es la multiplicación por la serie geométrica $\frac{1}{1-x}$. Como todos los coeficientes de $\frac{1}{1-x}$ son $1$, al multiplicar una OGF $A(x)$ por $\frac{1}{1-x}$ transformas la sucesión $(a_n)$ en su sucesión de sumas parciales. Esto te da un método algebraico rápido para sumar coeficientes o para encontrar el número de formas de elegir elementos cuando el orden de la selección implica un total acumulado.
El Producto de Cauchy (Convolución) Si $A(x) = \sum_{n=0}^{\infty} a_n x^n$ y $B(x) = \sum_{n=0}^{\infty} b_n x^n$, entonces su producto $C(x) = A(x)B(x)$ está dado por $C(x) = \sum_{n=0}^{\infty} c_n x^n$, donde: $$ c_n = \sum_{k=0}^n a_k b_{n-k} $$ Esto también lo puedes escribir usando el operador de extracción de coeficientes $[x^n]$: $$ x^n = \sum_{k=0}^n ([x^k]A(x)) \cdot ([x^{n-k}]B(x)) $$
Generalización a $m$ Funciones Para el producto de $m$ funciones generatrices $A_1(x) \dots A_m(x)$, el coeficiente de $x^n$ es: $$ [x^n] \prod_{j=1}^m A_j(x) = \sum_{k_1 + k_2 + \dots + k_m = n} a_{1, k_1} a_{2, k_2} \dots a_{m, k_m} $$ donde la suma se toma sobre todas las soluciones en enteros no negativos de $k_1 + \dots + k_m = n$.
Sumas Parciales Multiplicar una función generatriz por $\frac{1}{1-x}$ te da las sumas parciales de la sucesión: $$ \frac{A(x)}{1-x} = \sum_{n=0}^{\infty} \left( \sum_{k=0}^n a_k \right) x^n $$
Teorema: Sean $A(x) = \sum_{n=0}^{\infty} a_n x^n$ y $B(x) = \sum_{n=0}^{\infty} b_n x^n$ series de potencias formales. Entonces el coeficiente de $x^n$ en el producto $A(x)B(x)$ está dado por $c_n = \sum_{k=0}^n a_k b_{n-k}$.
Demostración: Empieza escribiendo el producto de las dos series infinitas: $$ A(x)B(x) = \left( \sum_{i=0}^{\infty} a_i x^i \right) \left( \sum_{j=0}^{\infty} b_j x^j \right) $$
Usando la propiedad distributiva para series de potencias formales, puedes expandir este producto multiplicando cada término de la primera serie por cada término de la segunda. Esto resulta en una sumatoria doble: $$ A(x)B(x) = \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} (a_i x^i)(b_j x^j) = \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} a_i b_j x^{i+j} $$
Para encontrar el coeficiente de una potencia específica $x^n$, tienes que juntar todos los pares de índices $(i, j)$ tales que la suma de sus exponentes sea $n$. Es decir, necesitas que $i + j = n$.
Puedes reagrupar los términos de la suma doble según el exponente total $n$. Toma $n = i + j$. Como $i$ y $j$ son enteros no negativos, para una $n$ fija, $i$ puede ir desde $0$ hasta $n$, y $j$ queda determinado por $j = n - i$.
Si escribes de nuevo la sumatoria agrupando los términos con el mismo exponente $x^n$: $$ A(x)B(x) = \sum_{n=0}^{\infty} \left( \sum_{i+j=n} a_i b_j \right) x^n $$
Al sustituir $j = n - i$ en la suma interna, haces que $i$ vaya de $0$ a $n$: $$ A(x)B(x) = \sum_{n=0}^{\infty} \left( \sum_{i=0}^n a_i b_{n-i} \right) x^n $$
Así, el coeficiente de $x^n$ en el producto es exactamente la convolución de las sucesiones: $$ c_n = \sum_{i=0}^n a_i b_{n-i} $$ $\square$