Introducción
Una función generatriz es un polinomio $a_0+a_1x+a_2x^2+\ldots+a_nx^n$ donde los coeficientes son números enteros positivos --y que representan la cardinalidad de algún conjunto (cuentan algo). El ejemplo prototipo de función generatriz es $(1+x)^n$. Como se sabe, los coeficientes de la expansión del binomio $(1+x)^n$ cuentan los subconconjuntos de $\{ 1,2,\ldots,n\}$. Es decir, el coeficiente $C(n,r)$ de $x^r$ es la solución al problema de calcular el número de subconjuntos de tamaño $ r $ del conjunto $\{ 1,2,\ldots,n\}$. (Tenemos aquí una respuesta en espera de la pregunta.)
Origen del modelo (de la respuesta genérica en espera de la pregunta)
La pregunta original a que responde esta función generatriz es: ¿de cuántas formas puedo elegir un subconjunto de $\{ 1,2,\ldots,n\}$?. Y, en su formulación, se razonaría de la siguiente manera: para formar un subconjunto, el primer elemento lo puedo elegir o no elegir; y para ello pongo $(1+x)$, donde el 1 está para la opción de no elegirlo, y la $x$ para la opción de sí elegirlo. Lo mismo es cierto para cada uno de los restantes elementos. Por tanto, el modelo es $(1+x)(1+x)(1+x)...(1+x)$ --con $ n $ paréntesis.
Todavía más en el origen de la invención de las funciones generatrices está la observación de que la expansión de, por ejemplo, $(1+a)(1+b)(1+c)(1+d)$, genera los subconjuntos de $\{ a,b,c,d\}$ como términos de la expresión algebraica resultante. (El lector debería ejecutar la expansión aplicando la regla distributiva y convencerse por sí mismo de ello.)
Pero, ¿si solamente quisiera el número de tales subconjuntos y no la lista de ellos? Bueno, en ese caso, hago $a=b=c=d=1$ y obtengo $2^4$. ¿Y si me interesara agrupar los subconjuntos por su tamaño? Bueno, el artefacto que hace el truco es asociar una $x$ a cada elemento: $(1+ax)(1+bx)(1+cx)(1+dx)$ agrupa los subconjuntos de tamaño $ r $ ($r=0,1,2,3,4$) como coeficientes de $x^r$. Y esto porque cada vez que elijo el elemento $b$ --por ejemplo-- también elijo de manera automática la $x$; de esta manera, el exponente de la $x$ es el contador del tamaño del subconjunto. (Como se puede apreciar, el truco es de un ingenio deslumbrante --y es un legado de la tradición dentro de la cultura matemática.)
Modelación (instancias de uso)
Con la misma idea que se explicó antes para los coeficientes binomiales, modelemos el siguiente
Instancia 1 (elección con restricciones)
¿De cuántas formas puede un aficionado a las matemáticas de concurso elegir problemas de MaTeTaM bajo las condiciones de que sean de las categorías Algebra, Combinatoria, o Números y que, por razones personales, sean a lo más dos de Algebra, a lo más uno de Combinatoria y a lo más 2 de Números?
Modelo (con función generatriz)
El modelo es $(1+x+x^2)(1+x)(1+x+x^2)$. Y el coeficiente de $x^r$ es el número de formas en que se pueden elegir $ r $ problemas de MaTeTaM bajo las restricciones dadas.
Instancia 2 (distribuciones)
Tengo monedas de 1,2,5,y 10 pesos en cantidades suficientes para completar, con cualquiera de ellas, una cantidad, digamos 100 pesos. ¿De cuántas formas puedo formar con ellas 100 pesos?
Modelo (con función generatriz)
Para formar los 100 pesos puedo tomar ninguna, una, dos, etc. monedas de 1 peso; y lo mismo es cierto de las monedas de 2, de 5 y de 10. Si queremos generar las posibilidades mediante una expansión de un producto de polinomios, el contador tiene que ir en el exponente: las monedas de 2 las representamos con $x^2$ (por cada moneda de 2 pesos que elija para formar los 100 pesos elijo también automáticamente la $x^2$) . De manera análoga, procedo con las demás. Entonces el modelo sería $$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^5+x^10+...)(1+x^10+x^20+...).$$ Y la respuesta a la pregunta sería: el coeficiente de $x^100$ en la expansión de ese producto de polinomios. (Hemos transformado un problema de combinatoria en uno de álgebra. Y, bueno, si uno sabe algo de álgebra, el encontrar ese coeficiente no debe ser muy difícil de calcular.)
Nota: De hecho, el modelo más básico es la ecuación diofantina $x+2y+5z+10w=100$, y se ve que ésta es la que se incorpora en el exponente de la $x$ (de la cual queremos encontrar el coeficiente).
Cálculo de la función generatriz dados sus coeficientes de manera recursiva
Consideremos la sucesión de Fibonacci $F(0)=0,F(1)=1$ y, a partir de aquí, se tiene la recurrencia $F(n)=F(n-1)+F(n-2).$ Sea $F(x)$ la función que genera esos coeficientes. Entonces $F(x)=F(0)+F(1)x+F(2)x^2+\ldots$. Pero podemos aplicar la recurrencia (a partir de $n=2$) y obtener, después de algunas manipulaciones algebraicas, $F(x)(1+x+x^2)=x$
Ejemplo final (de modelación recursiva)
Encontrar el número de n-cadenas de ceros y unos que no contienen el patrón $111$
Solución: Sea $S_n$ el número de tales cadenas. Estas cadenas se pueden clasificar en tres tipos: o bien la cadena empieza con 0, o bien con 10 o bien con 11. De aquí que $S_n=S_{n-1}+S_{n-2}+S_{n-3}.$ Y las condiciones iniciales son: $S_1=2, S_2=4, S_3=7.$
Moraleja
Una vez que sabemos que los problemas combinatorios se pueden convertir en algebraicos (si es que podemos modelarlos como función generatriz), lo que sigue es aprender la técnica algebraica de las funciones generatrices. Es decir, sería muy productivo (en términos de desempeño en concursos) aprender la modelación de problemas combinatorios en términos de funciones generatrices y/o recurrencias --si es que también aprendemos el álgebra asociada. (Una doble tarea. Es por eso que la recursión y las funciones generatrices están en los últimos capítulos de los libros de combinatoria: "No les enseñes eso a los chicos, porque no le van a entender --y van a ir con el director a decirle que no sabes explicar... mejor deja que se pase el semestre con el Triángulo de Pascal...":)
Los saluda
jmd