Funciones generatrices aplicadas a problemas combinatorios

Ejemplos:

1.- ¿De cuantas formas se pueden colocar 7 bolas idénticas en 5 urnas de las cuales, tres tienen capacidad hasta 1 bola y las otras dos capacidad de hasta cuatro?

La función generatriz será:

> g:=x->(1+x+x^2+x^3+x^4)^2*(1+x)^3;

> expand (g(x));

la respuesta es, como se ve, 28. Podríamos haberla obtenido sin expandir el polinomio, haciendo:

> coeff(g(x),x,7);

2.- ¿De cuantas formas se pueden colocar 20 objetos iguales en tres urnas de las cuales, una tiene capacidad ilimitada y las otras dos pueden contener cualquier número impar hasta 5?

La función generatriz será:

> gg:=x->(x+x^3+x^5)^2*(1/(1-x));

> p1:=taylor(gg(x),x=0,22);

> coeff(p1,x,20);

La solución es 9.

Recuérdese que el coeficiente del término k de p1 es el valor de la derivada k -ésima de gg(x) evaluada en 0 y dividida por k! . Por ejemplo:

> (subs(x=0,diff(gg(x),x$4)))/4!;

que coincide con el coeficiente de grado cuatro.

3.- Encontrar el número de soluciones enteras comprendidas entre 3 y 8 (ambos inclusive) de a+b+c+d=24 .

Este problema es equivalente a repartir 24 objetos en cuatro urnas de capacidad mínima 3 y máxima 8. Por lo tanto, la función generatriz será:

> ggg:=x->(x^3+x^4+x^5+x^6+x^7+x^8)^4;

y la solución será:

> coeff(ggg(x),x,24);

4.- Encontrar la función generatriz para calcular las distintas formas de pagar una cantidad con monedas de peseta, duro y cinco-duros. ¿Cual es la solución para 500 Pts?

La función generatriz será:

> f:=x->1/(1-x)*(1/(1-x^5))*(1/(1-x^25));

> coeff(taylor(f(x),x=0, 501),x,500);

por lo tanto, hay 1071 formas de pagar.
 
 
 

Ejercicios:

1.- Encontrar las funciones generatrices para las formas de distribuir 40 objetos entre cinco urnas:

cuando no hay ninguna restricción en el número de objetos en cada urna,

cuando cada urna debe contener al menos un objeto,

cuando cada urna contiene al menos tres objetos,

cuando cada urna contiene un número par de objetos.

2.- Si arrojamos un dado 5 veces ¿De cuantas maneras puede salir de suma 15? ¿Cual es la probabilidad de conseguir sumar 15? ¿Cual es la suma que tiene más probabilidad de salir?