mate

9 FUNCIONES GENERATRICES
En este capítulo y el siguiente continuaremos nuestro estudio de la enumeración con el importante concepto de la función generatriz.
El problema de hacer selecciones, con repeticiones permitidas, fue estudiado en el capítulo 1. Ahí tratamos de obtener, por ejemplo, el número de soluciones enteras de la ecuación c1 + c2 + c3 + c4= 25 donde ci ≥ 0 para todo 1 ≤ i ≤ 4.En el capítulo 8, con e1 principio de inclusión y exclusión, fuimos capaces de resolver una versión más restringida del problema, como c1 + c2 + c3 + c4= 25 con 0 ≤ ci ≤10 para todo 1 ≤ i ≤4. Si, además, quisiéramos que c2 fuera par y c3 un múltiplo de 3, podríamos aplicar los resultados de los capítulos 1 y 8 en varios subcasos.
La fuerza de la función generatriz descansa en que no sólopermite resolver los tipos de problemas ya analizados anteriormente sino que también ayuda en situaciones nuevas donde pueden aparecer más restricciones
9.1 Ejemplos introductorios

En lugar de definir en este punto una función generatriz, examinaremos algunos ejemplos para derivar la idea a partir de ellos. Veremos que ya hemos tratado este concepto en situaciones anteriores

Ejemplo 9.1
Ensus compras del sábado, Mónica compró 12 naranjas para sus hijos, Graciela, María y Francisco. ¿De cuántas formas puede ella distribuir las naranjas de tal forma que Graciela obtenga al menos cuatro y Mana y Francisco obtengan al menos dos, sin que Francisco no obtenga más de cinco? La tabla 9.1 enumera todas las distribuciones posibles. Vemos que tenemos todas las soluciones enteras de la ecuaciónc1 + c2 + c3 = 12 tal que 4 ≤ c1 , 2 ≤ c2 y 2≤ c3 ≤ 5.
Al considerar los primeros dos casos en esta tabla, encontramos las soluciones 4 + 3 + 5 = 12 y 4 + 4 + 4=12. ¿Sucedió algo así en nuestras experiencias algebraicas anteriores? Al multiplicar polinomios añadimos las potencias de la variable, y aquí, al multiplicar los tres polinomios,
(x4 + x5+ x6 + x7 + x8)(x2 + x3 + x4 + x5 + x6)(x2+ x3 + x4 + x5),

dos de los caminos para obtener xn son como sigue:
Tabla 9.1
G
M
F

G
M
F
4
3
5

5
5
2
4
4
4

6
2
4
4
5
3

6
3
3
4
6
2

6
4
2
5
2
5

7
2
3
5
3
4

7
3
2
5
4
3

8
2
2
1)Del producto x4 x3x5, donde x4 se toma de (x4 + x5 +…. + x8), x3 de (x2 + x3 … + x6) y x5 de (x2 + x3 +…. + x5)
2)Del producto x4 x4 x4, donde el primerx4 se encuentra en el primer polinomio, el segundo x4 en el segundo polinomio y el tercer x4 en el tercer polinomio.

Al examinar el producto

(x4 + x5 + x6 + x7 + x8)(x2 + x3 + x4 + x5 + x6)(x2 + x3 + x4 + x5)

con más cuidado, nos damos cuenta de que obtenemos el producto x i x j xk para toda terna (i, j, k) que aparece en la tabla 9.1. En consecuencia, el coeficiente de x12 en
f(x) =(x4 + x5 + … + x8)(x2 + x3 + …+ x6)(x2 + x3 + … + x5)

cuenta el número buscado de distribuciones, 14. La función f(x) es la función generatriz para las distribuciones.
Pero, ¿de dónde salieron los factores en este producto?
Por ejemplo, el factor x4 + x3 + x6 + x7 + x8, indica que podemos dar a Graciela 4 o 5 ó 6 o 7 u 8 naranjas. Una vez más hicimos uso de la interacción entre la o exclusivay la suma ordinaria. El coeficiente de cada potencia de x es 1 ya que, considerando las naranjas como objetos idénticos, sólo hay una forma de darle a Graciela cuatro naranjas, una forma de darle cinco naranjas y así sucesivamente. Como María y Francisco deben recibir cada uno al menos dos naranjas, los otros términos (x2 + x3 +…. + x6) y (x2 +x3 + … +x5) comienzan con x2 y, en el caso deFrancisco, nos detenemos en x5 para que no reciba más de cinco naranjas. (¿Por qué detenemos en x6 el término de María?)
La mayoría de nosotros nos hemos convencido razonablemente de que el coeficiente de x12 en f(x) nos da la respuesta. Sin embargo, algunos serán un poco escépticos acerca de esta nueva idea. Parece que sería más rápido enumerar los casos de la tabla 9.1 que multiplicar los tres...