Armando FGOs

Teoría

Una Función Generatriz Ordinaria (FGO) es una serie de potencias formal que sirve para codificar una sucesión de números $(a_n){n \ge 0}$ como los coeficientes de un polinomio o de una serie infinita. Específicamente, para una sucesión $a_0, a_1, a_2, \dots$, la FGO correspondiente la definimos como $A(x) = \sum{n=0}^{\infty} a_n x^n$. En el contexto de la combinatoria, a la variable $x$ la sueles tratar como un marcador de posición formal o una "etiqueta" en lugar de un número específico; por lo general no te importa la convergencia de la serie, sino la estructura algebraica que te da. Esta técnica te permite manipular toda la sucesión al mismo tiempo como un solo objeto algebraico.

Armar una FGO es una estrategia muy potente porque transforma problemas combinatorios discretos —como resolver recurrencias, contar particiones o encontrar formas cerradas para sumas— en problemas algebraicos. La fuerza de este método está en la correspondencia entre las operaciones con sucesiones y las operaciones con funciones. Por ejemplo, desplazar una sucesión corresponde a multiplicar por $x$, y contar las formas de combinar dos estructuras independientes suele corresponder a multiplicar sus funciones generatrices.

La intuición para armar una FGO a veces se explica con la analogía del "tendedero": la serie de potencias es un tendedero donde