Funciones generatrices aplicadas a problemas combinatorios

Ejemplos: 1.- De cuantas formas se pueden colocar 7 bolas idnticas en 5 urnas de las

cuales, tres tienen capacidad hasta 1 bola y las otras dos capacidad de hasta cuatro?

La funcin generatriz ser:

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

g := x → (1 + x + x^{2} + x^{3} + x^{4})^{2} (1 + x)^{3}

> expand (g(x));

1 + 5 x + 12 x^{2} + 20 x^{3} + 28 x^{4} + 34 x^{5} + 34 x^{6} + 28 x^{7} + 20 x^{8} + 12 x^{9} + 5 x^{10} + x^{11}

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

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

28

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 nmero impar hasta 5?

La funcin generatriz ser:

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

gg := x → \frac{(x + x^{3} + x^{5})^{2}}{1 − x}

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

p1 := x^{2} + x^{3} + 3 x^{4} + 3 x^{5} + 6 x^{6} + 6 x^{7} + 8 x^{8} + 8 x^{9} + 9 x^{10} + 9 x^{11} + 9 x^{12} + 9 x^{13} + 9 x^{14}+ 9 x^{15} + 9 x^{16} + 9 x^{17} + 9 x^{18} + 9 x^{19} + 9 x^{20} + 9 x^{21} + O(x^{22})

> coeff(p1,x,20);

9

La solucin es 9. Recurdese que el coeficiente del trmino 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!;

3

que coincide con el coeficiente de grado cuatro. 3.- Encontrar el nmero 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 mnima 3 y mxima 8. Por lo tanto, la funcin generatriz ser:

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

ggg := x → (x^{3} + x^{4} + x^{5} + x^{6} + x^{7} + x^{8})^{4}

y la solucin ser:

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

125 Ejercicios: 1.- Encontrar las funciones generatrices para las formas de distribuir 40 ob-

jetos entre cinco urnas: • cuando no hay ninguna restriccin en el nmero 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 nmero par de objetos. 2.-