Función generatriz (de una sucesión)

Es una transformación de una sucesión de números $a_0, a_1,\ldots$ en una serie de potencias $a_0+a_1x+a_2x^2+\ldots$, la cual se puede expresar mediante una expresión algebraica cerrada. Por ejemplo, $(1+x)^n$ es función generatriz del número de subconjuntos de tamaño $r$ (para $r=0,1,2,\ldots$) tomados de un conjunto de tamaño $n$  --pues $(1+x)^n=C(n,0)+C(n,1)x+C(n,2)x^2+...+C(n,n)x^n.$

En su uso en la solución de problemas combinatorios, es indispensable saber modelar un problema en términos de funciones generatrices. Y esto sólo es posible conociendo el "código" de la transformación. En el ejemplo del binomio de Newton, la lógica que está por detrás de la transformación sería más o menos así:

--Para elegir un subconjunto de tamaño $r$ de $\{1,2,\ldots, n\}$ se decide en $n$ etapas etiquetando cada elemento con un $0$ o un $1$ (lo cual equivale a incluir o no incluir el elemento);

--y un subconjunto se forma mediante $n$ elecciones de inclusión-exclusión, y cada elección se puede representar mediante el binomio $1+x$ --$1$ si se excluye, $x$ si se incluye.

--Entonces, en la expansión de $(1+x)^n$, el número de subconjuntos de tamaño $r$ es el coeficiente de $x^r$.

--Notemos finalmente que, de acuerdo a la regla distributiva, en la expansión de un producto como $(1+a)(1+b)(1+c)(1+d)$, cada término de la expansión se forma eligiendo un término de cada paréntesis y cada término de la expansión se puede ver como un subconjunto de $\{a,b,c,d\}$;

--para registrar el tamaño del subconjunto se añade la $x$: $(1+ax)(1+bx)(1+cx)(1+dx).$ Y si sólo nos interesa el número de subconjuntos de cada uno de los tamaño $r=0,1,2,3,4$, basta con hacer $a=b=c=d=1.$ (Posiblemente la función generatriz sea el truco más ingenioso jamás inventado en matemáticas.)