Inclusión-Exclusión mediante generatrices.

Inclusión-Exclusión mediante generatrices.

de Franco Pelua Camacho -
Número de respuestas: 2

Hola, buenas noches. 

Me preguntaba si es posible resolver problemas típicos del principio de inclusión-exclusión mediante el uso de funciones generatrices. 

Yo estuve intentando con este ejercicio (del práctico 3) en particular: 

Y lo modele tal que la respuesta seria el coeficiente de  x^{18} en la función generatriz  (x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6})^{6} , que no es más que la geométrica finita de orden 6, por lo tanto es lo mismo: [x^{18}] en  \frac{(1-x^{7})}{1-x} .

Esta expresión se puede separar como [x^{18}] en (1-x^7)^6 \times (1-x)^{-6}

Y desarrollando el primer término mediante el binomio de Newton, obtenemos: 

[x^{18}] en (1 - 6x^7 + 15x^{14} - 20x^{21} + 15x^28 - 6x^{35} + x^{42}) \times (1-x)^{-6}

A partir de acá no sabría como proseguir. ¿Por qué al hacer la distributiva, los términos que tienen grado 21 en adelante no me servirían verdad? Porque me quedaría algo de grado mayor a 18 multiplicado por algo, que en todo caso sobrepasará en grado al 18 y no son los casos que busco contar. El problema es que si solo considero la distributiva con los términos de grado 0, 7 y 14, y calculo por separado los coeficientes, al hacer la respectiva suma no obtengo la respuesta correcta. Es decir, si hago:

[x^{18}] en (1-x)^{-6}  -6 \times [x^{11}] en (1-x)^{-6}  + 15 \times [x^4] en (1-x)^-6

Claramente, el planteo tiene que estar mal, o la suposición que hago de no contar los elementos con grado mayor a 18, pero no sabría donde esta el error exactamente, y creo que sería de gran ayuda entenderlo. 

En respuesta a Franco Pelua Camacho

Re: Inclusión-Exclusión mediante generatrices.

de Gabriel Mello -
Hola Franco.

Hay varios errores en tu planteo. Paso a explicarte.

Primero que nada, los posibles múltiplos de 18 que se pueden obtener como suma de 6 tiradas de un dado son 18 o tambien 36, que se puede obtener de una única forma (si salen todos 6) por lo que en primer lugar te faltó ese caso. Sacando eso, si sumamos ese caso aparte sí es correcto buscar el coeficiente de  x^18 en alguna función generatriz y después lo que de eso sumarle uno.

Segundo, la función generatriz que planteás es correcta: separás en 6 etapas idénticas cuyo orden importa y tales que el resultado de cada una de ellas no afecta la cantidad de resultados posibles de las siguientes por lo que aplicás la regla del producto. Más aún en cada etapa hay 6 resultados exhaustivos y excluyentes por lo que separás por la regla de la suma. Cada resultado entre 1 y 6 viene representado por el monomio con el exponente correspondiente. Hasta acá todo perfecto, el problema es que el salto que das inmediatamente después es falso.

La serie geométrica (finita o infinita) arranca en 1, por lo que todas las cuentas que siguen están mal. Si sacamos un factor común de  x dentro de la base nos queda  x^6 ( 1 + x + x^2 + x^3 + x^4 + x^5)^6 y ahí sí tenés una serie geométrica finita que podés sustituir por  \frac{1-x^6}{1-x} . Te dejo que remates el cálculo y me cuentes si te da bien.

Saludos,
Gabriel
En respuesta a Gabriel Mello

Re: Inclusión-Exclusión mediante generatrices.

de Franco Pelua Camacho -
Genial Gabriel, muchísimas gracias! ahora si salió y quedo todo más claro. Al final se llega a 3432 que es la respuesta a la que se llegó usando inclusión-exclusión en el práctico, así que quedo pronto. Me sorprende lo fácil que resultan estos ejercicios usando generatrices, el tema es usarlas bien jajaja.

Gracias de nuevo, saludos!