Prácticas de Matemáticas Discretas II

Práctica 1. Matemáticas Discretas II

Manuel Álvarez Díaz

Facultad de Informática 3 Noviembre 1997

e-mail: i3026@cecafi.fi.udc.es

Escribir un trabajo (formato ps o dvi) donde se recoja la solución de los ejercicios propuestos junto con la explicación detallada de las herramientas (procedimientos en Maple ...) y métodos usados para su solución.

Una primera tanda de ejercicios es la que sigue:

1 Encontrar las funciones generatrices para las formas de distribuir 40 objetos entre 5 cajas.

NOTA 1: Sabemos calcular la función generatriz para el número de formas de distribuir k objetos en N urnas, pudiendo haber en cada urna un número máximo de L objetos (a fijar). (para cualquier k).

(x^{0} + x^{1} + x^{2} + … + x^{L})^{N} = (∑_{i=1}^{L} x^{i})^{N}

Y en este caso el coeficiente k-ésimo de ese desarrollo es el número de formas de colocar k objetos en N urnas con 0 ó 1 ó 2 … ó L objetos cada una.

En este caso k=40 ⇒ el resultado es un valor numérico, no una función generatriz. En concreto, el resultado será el coeficiente k-ésimo del desarrollo en serie de Taylor en x=0 de la función generatriz anterior. Luego el enunciado debería decir lo siguiente: encontrar las formas de distribuir 40 objetos entre 5 cajas utilizando para ello las funciones generatrices.

Y esta última aclaración es necesaria debido a que hay otras formas posibles de afrontar este mismo problema. Otra forma posible es plantear la ecuación x_{1} +x_{2} +…+x_{n} = k, y el problema es el siguiente: ¿ Cuál es el número de soluciones enteras de la ecuación anterior? La solución es

CR(n, k) = \binom{k + n − 1}{k}

NOTA 2: En el caso de que L sea un número finito, ese desarrollo es un polinomio, y el desarrollo en serie de Taylor de un polinomio es trivial; lo cual quiere decir que el coeficiente del término k-ésimo del desarrollo en serie de Taylor de un polinomio coincide con el coeficiente del término de grado k del polinomio en cuestión.

NOTA 3: La función que extrae el coeficiente k-ésimo de un polinomio es :

coeff(P(x),x,k);

y la que extrae el coeficiente k-ésimo del desarrollo en serie de Taylor de una función generatriz racional es:

with(genfunc):
rgf_term(F(x),x,k);

(a) cuando no hay restricciones para el número de objetos en cada caja.

Que no haya restricciones quiere decir, en este caso, que en cada caja se pueden colocar de 0 a 40 objetos. La función generatriz genérica para colocar k objetos en 5 cajas de a lo sumo 40 objetos cada una es

> F := x -> (sum ('x**n','n'=0..40))^5;

F := x ↦ (∑_{n=0}^{40} x^{n})^{5}

que si desarrollamos queda :

F (x) := (1 + x + x^{2} + x^{3} + x^{4} + x^{5} + … + x^{35} + x^{36} + x^{37} + x^{38} + x^{39} + x^{40})^{5}

Pero a nosotros nos interesa colocar 40 objetos(k=40) → queremos extraer el coeficiente 40 del desarrollo anterior. Pero antes de aplicar coeff “expandimos” la función para obtener un polinomio en la forma a_{0} + a_{1}x + a_{2}x^{2} + … que por tratarse de un polinomio, coincide con su desarrollo en serie de Taylor en x=0.

> expand(F(x));
o
> taylor(F(x),x=0,300)

(1 + 5 x + 15 x^{2} + 35 x^{3} + 70 x^{4} + 126 x^{5} + 210 x^{6} + 330 x^{7} + 495 x^{8} + 715 x^{9} + 1001 x^{10}+1365 x^{11}+1820 x^{12}+2380 x^{13}+3060 x^{14}+3876 x^{15}+4845 x^{16}+5985 x^{17}+ 7315 x^{18} + 8855 x^{19} + 10626 x^{20} + 12650 x^{21} + 14950 x^{22} + 17550 x^{23} + 20475 x^{24} + 23751 x^{25} +27405 x^{26} +31465 x^{27} +35960 x^{28} +40920 x^{29} +46376 x^{30} +52360 x^{31} + 58905 x^{32}+66045 x^{33}+73815 x^{34}+82251 x^{35}+91390 x^{36}+101270 x^{37}+111930 x^{38}+ 123410 x^{39} + 135751 x^{40} + 148990 x^{41} + 163160 x^{42} + 178290 x^{43} + 194405 x^{44} + 211526 x^{45} + 229670 x^{46} + 248850 x^{47} + 269075 x^{48} + 290350 x^{49} + 312676 x^{50} + 336050 x^{51} + 360465 x^{52} + 385910 x^{53} + 412370 x^{54} + 439826 x^{55} + 468255 x^{56} + 497630 x^{57} + 527920 x^{58} + 559090 x^{59} + 591101 x^{60} + 623910 x^{61} + 657470 x^{62} + 691730 x^{63} + 726635 x^{64} + 762126 x^{65} + 798140 x^{66} + 834610 x^{67} + 871465 x^{68} + 908630 x^{69} + 946026 x^{70} + 983570 x^{71} + 1021175 x^{72} + 1058750 x^{73} + 1096200 x^{74} + 1133426 x^{75}+1170325 x^{76}+1206790 x^{77}+1242710 x^{78}+1277970 x^{79}+1312451 x^{80}+ 1346030 x^{81}+1378590 x^{82}+1410020 x^{83}+1440215 x^{84}+1469076 x^{85}+1496510 x^{86}+ 1522430 x^{87}+1546755 x^{88}+1569410 x^{89}+1590326 x^{90}+1609440 x^{91}+1626695 x^{92}+ 1642040 x^{93}+1655430 x^{94}+1666826 x^{95}+1676195 x^{96}+1683510 x^{97}+1688750 x^{98}+ 1691900 x^{99} + 1692951 x^{100} + 1691900 x^{101} + 1688750 x^{102} + 1683510 x^{103} + 1676195 x^{104} + 1666826 x^{105} + 1655430 x^{106} + 1642040 x^{107} + 1626695 x^{108} + 1609440 x^{109} + 1590326 x^{110} + 1569410 x^{111} + 1546755 x^{112} + 1522430 x^{113} + 1496510 x^{114} + 1469076 x^{115} + 1440215 x^{116} + 1410020 x^{117} + 1378590 x^{118} + 1346030 x^{119} + 1312451 x^{120} + 1277970 x^{121} + 1242710 x^{122} + 1206790 x^{123} + 1170325 x^{124} + 1133426 x^{125} + 1096200 x^{126} + 1058750 x^{127} + 1021175 x^{128} + 983570 x^{129}+946026 x^{130}+908630 x^{131}+871465 x^{132}+834610 x^{133}+798140 x^{134}+ 762126 x^{135}+726635 x^{136}+691730 x^{137}+657470 x^{138}+623910 x^{139}+591101 x^{140}+ 559090 x^{141}+527920 x^{142}+497630 x^{143}+468255 x^{144}+439826 x^{145}+412370 x^{146}+ 385910 x^{147}+360465 x^{148}+336050 x^{149}+312676 x^{150}+290350 x^{151}+269075 x^{152}+ 248850 x^{153}+229670 x^{154}+211526 x^{155}+194405 x^{156}+178290 x^{157}+163160 x^{158}+ 148990 x^{159} +135751 x^{160} +123410 x^{161} +111930 x^{162} +101270 x^{163} +91390 x^{164} + 82251 x^{165} + 73815 x^{166} + 66045 x^{167} + 58905 x^{168} + 52360 x^{169} + 46376 x^{170} + 40920 x^{171} + 35960 x^{172} + 31465 x^{173} + 27405 x^{174} + 23751 x^{175} + 20475 x^{176} + 17550 x^{177}+14950 x^{178}+12650 x^{179}+10626 x^{180}+8855 x^{181}+7315 x^{182}+5985 x^{183}+ 4845 x^{184} + 3876 x^{185} + 3060 x^{186} + 2380 x^{187} + 1820 x^{188} + 1365 x^{189} + 1001 x^{190} + 715 x^{191} + 495 x^{192} + 330 x^{193} + 210 x^{194} + 126 x^{195} + 70 x^{196} + 35 x^{197} + 15 x^{198} + 5 x^{199} + x^{200})

Y ahora extraemos el término 40:

> coeff(expand(F(x)),x,40);

135751 Ese resultado es el mismo que obtenemos si planteamos la ecuación x_{1} + x_{2} +

x_{3} + x_{4} + x_{5} = 40 y calculamos el número de soluciones enteras positivas:

> binomial(5+40-1,40);

135751

(b) cuando cada caja tiene por lo menos 1 objeto.

Que cada caja tenga como mínimo 1 objeto ⇒ el número de formas en que se pueden colocar 4 objetos o menos es 0; luego en este caso en la función generatriz tenemos que eliminar los términos menores que x^{5}; es decir, el sumatorio empieza en 1 en lugar de en 0:

> F := x -> (sum ('x**n','n'=1..40))^5;

F := x ↦ (∑_{n=1}^{40} x^{n})^{5}

que si desarrollamos queda :

F (x) := (x + x^{2} + x^{3} + x^{4} + x^{5} + … + x^{35} + x^{36} + x^{37} + x^{38} + x^{39} + x^{40})^{5}

Si expandimos el polinomio anterior, observamos que no aparecen términos de grado menor que 5 : (x^{5} + 5 x^{6} + 15 x^{7} + 35 x^{8} + 70 x^{9} + 126 x^{10} + 210 x^{11} + 330 x^{12} + 495 x^{13} + 715 x^{14} + 1001 x^{15} + 1365 x^{16} + 1820 x^{17} + 2380 x^{18} + 3060 x^{19} + 3876 x^{20} + 4845 x^{21} + 5985 x^{22} + 7315 x^{23} + 8855 x^{24} + 10626 x^{25} + 12650 x^{26} + 14950 x^{27} + 17550 x^{28} + 20475 x^{29} +23751 x^{30} +27405 x^{31} +31465 x^{32} +35960 x^{33} +40920 x^{34} +46376 x^{35} + 52360 x^{36}+58905 x^{37}+66045 x^{38}+73815 x^{39}+ 82251 x^{40}+91390 x^{41}+101270 x^{42}+ 111930 x^{43} + 123410 x^{44} + 135746 x^{45} + 148970 x^{46} + 163110 x^{47} + 178190 x^{48} + 194230 x^{49} + 211246 x^{50} + 229250 x^{51} + 248250 x^{52} + 268250 x^{53} + 289250 x^{54} + 311246 x^{55} + 334230 x^{56} + 358190 x^{57} + 383110 x^{58} + 408970 x^{59} + 435746 x^{60} + 463410 x^{61} + 491930 x^{62} + 521270 x^{63} + 551390 x^{64} + 582246 x^{65} + 613790 x^{66} + 645970 x^{67} + 678730 x^{68} + 712010 x^{69} + 745746 x^{70} + 779870 x^{71} + 814310 x^{72} + 848990 x^{73} + 883830 x^{74} + 918746 x^{75} + 953650 x^{76} + 988450 x^{77} + 1023050 x^{78} + 1057350 x^{79}+1091246 x^{80}+1124630 x^{81}+1157390 x^{82}+1189410 x^{83}+1220570 x^{84}+ 1250756 x^{85}+1279860 x^{86}+1307780 x^{87}+1334420 x^{88}+1359690 x^{89}+1383506 x^{90}+ 1405790 x^{91}+1426470 x^{92}+1445480 x^{93}+1462760 x^{94}+1478256 x^{95}+1491920 x^{96}+ 1503710 x^{97} + 1513590 x^{98} + 1521530 x^{99} + 1527506 x^{100} + 1531500 x^{101} + 1533500 x^{102} + 1533500 x^{103} + 1531500 x^{104} + 1527506 x^{105} + 1521530 x^{106} + 1513590 x^{107} + 1503710 x^{108} + 1491920 x^{109} + 1478256 x^{110} + 1462760 x^{111} + 1445480 x^{112} + 1426470 x^{113} + 1405790 x^{114} + 1383506 x^{115} + 1359690 x^{116} + 1334420 x^{117} + 1307780 x^{118} + 1279860 x^{119} + 1250756 x^{120} + 1220570 x^{121} + 1189410 x^{122} + 1157390 x^{123} + 1124630 x^{124} + 1091246 x^{125} + 1057350 x^{126} + 1023050 x^{127}+988450 x^{128}+953650 x^{129}+918746 x^{130}+883830 x^{131}+848990 x^{132}+ 814310 x^{133}+779870 x^{134}+745746 x^{135}+712010 x^{136}+678730 x^{137}+645970 x^{138}+ 613790 x^{139}+582246 x^{140}+551390 x^{141}+521270 x^{142}+491930 x^{143}+463410 x^{144}+ 435746 x^{145}+408970 x^{146}+383110 x^{147}+358190 x^{148}+334230 x^{149}+311246 x^{150}+ 289250 x^{151}+268250 x^{152}+248250 x^{153}+229250 x^{154}+211246 x^{155}+194230 x^{156}+ 178190 x^{157}+163110 x^{158}+148970 x^{159}+135746 x^{160}+123410 x^{161}+111930 x^{162}+ 101270 x^{163} + 91390 x^{164} + 82251 x^{165} + 73815 x^{166} + 66045 x^{167} + 58905 x^{168} + 52360 x^{169} + 46376 x^{170} + 40920 x^{171} + 35960 x^{172} + 31465 x^{173} + 27405 x^{174} + 23751 x^{175} + 20475 x^{176} + 17550 x^{177} + 14950 x^{178} + 12650 x^{179} + 10626 x^{180} + 8855 x^{181} + 7315 x^{182} + 5985 x^{183} + 4845 x^{184} + 3876 x^{185} + 3060 x^{186} + 2380 x^{187} + 1820 x^{188} + 1365 x^{189} + 1001 x^{190} + 715 x^{191} + 495 x^{192} + 330 x^{193} + 210 x^{194} + 126 x^{195} + 70 x^{196} + 35 x^{197} + 15 x^{198} + 5 x^{199} + x^{200})

Y como en el caso anterior, como queremos colocar 40 objetos, k=40, el resultado buscado es el coeficiente del término 40

> coeff(expand(F(x)),x,40);

82251 El mismo resultado que el si calculásemos el número de soluciones enteras positivas de la ecuación x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 35. La ecuación ha cambiado con respecto a la del apartado anterior, puesto que como cada caja debe tener al menos 1 bola, hay 5 bolas previamente fijadas y por lo tanto no hay que repartirlas.

> binomial(5+35-1,35);

82251

(c) cuando cada caja tiene por lo menos 3 objetos.

Se procede como en los casos anteriores. Como ahora cada caja debe tener como mínimo 3 objetos, los coeficientes de los términos de grado menor que 5 ∗ 3 deben ser 0 (no se pueden repartir menos de 15 objetos). Luego, el sumatorio de la función generatriz comenzará en 3:

> F := x -> (sum ('x**n','n'=3..40))^5;

F := x ↦ (∑_{n=3}^{40} x^{n})^{5}

que si desarrollamos queda :

F (x) := (x^{3} + x^{4} + x^{5} + … + x^{35} + x^{36} + x^{37} + x^{38} + x^{39} + x^{40})^{5}

Si expandimos el polinomio anterior, observamos que no aparecen términos de grado menor que 15 : (x^{15} + 5 x^{16} + 15 x^{17} + 35 x^{18} + 70 x^{19} + 126 x^{20} + 210 x^{21} + 330 x^{22} + 495 x^{23} + 715 x^{24} + 1001 x^{25} + 1365 x^{26} + 1820 x^{27} + 2380 x^{28} + 3060 x^{29} + 3876 x^{30} + 4845 x^{31} + 5985 x^{32} + 7315 x^{33} + 8855 x^{34} + 10626 x^{35} + 12650 x^{36} + 14950 x^{37} + 17550 x^{38}+20475 x^{39}+ 23751 x^{40}+27405 x^{41}+31465 x^{42}+35960 x^{43}+40920 x^{44}+ 46376 x^{45} +52360 x^{46} +58905 x^{47} +66045 x^{48} +73815 x^{49} +82251 x^{50} +91390 x^{51} + 101270 x^{52} + 111925 x^{53} + 123385 x^{54} + 135676 x^{55} + 148820 x^{56} + 162835 x^{57} + 177735 x^{58} + 193530 x^{59} + 210226 x^{60} + 227825 x^{61} + 246325 x^{62} + 265720 x^{63} + 286000 x^{64} + 307151 x^{65} + 329155 x^{66} + 351990 x^{67} + 375630 x^{68} + 400045 x^{69} + 425201 x^{70} + 451060 x^{71} + 477580 x^{72} + 504715 x^{73} + 532415 x^{74} + 560626 x^{75} + 589290 x^{76} + 618345 x^{77} + 647725 x^{78} + 677360 x^{79} + 707176 x^{80} + 737095 x^{81} + 767035 x^{82} + 796910 x^{83} + 826630 x^{84} + 856101 x^{85} + 885225 x^{86} + 913900 x^{87} + 942020 x^{88} + 969475 x^{89} + 996151 x^{90} + 1021940 x^{91} + 1046740 x^{92} + 1070455 x^{93} + 1092995 x^{94}+1114276 x^{95}+1134220 x^{96}+1152755 x^{97}+1169815 x^{98}+1185340 x^{99}+ 1199276 x^{100} + 1211575 x^{101} + 1222195 x^{102} + 1231100 x^{103} + 1238260 x^{104} + 1243651 x^{105} + 1247255 x^{106} + 1249060 x^{107} + 1249060 x^{108} + 1247255 x^{109} + 1243651 x^{110} + 1238260 x^{111} + 1231100 x^{112} + 1222195 x^{113} + 1211575 x^{114} + 1199276 x^{115} + 1185340 x^{116} + 1169815 x^{117} + 1152755 x^{118} + 1134220 x^{119} + 1114276 x^{120} + 1092995 x^{121} + 1070455 x^{122} + 1046740 x^{123} + 1021940 x^{124} + 996151 x^{125}+969475 x^{126}+942020 x^{127}+913900 x^{128}+885225 x^{129}+856101 x^{130}+ 826630 x^{131}+796910 x^{132}+767035 x^{133}+737095 x^{134}+707176 x^{135}+677360 x^{136}+ 647725 x^{137}+618345 x^{138}+589290 x^{139}+560626 x^{140}+532415 x^{141}+504715 x^{142}+ 477580 x^{143}+451060 x^{144}+425201 x^{145}+400045 x^{146}+375630 x^{147}+351990 x^{148}+ 329155 x^{149}+307151 x^{150}+286000 x^{151}+265720 x^{152}+246325 x^{153}+227825 x^{154}+ 210226 x^{155}+193530 x^{156}+177735 x^{157}+162835 x^{158}+148820 x^{159}+135676 x^{160}+ 123385 x^{161} + 111925 x^{162} + 101270 x^{163} + 91390 x^{164} + 82251 x^{165} + 73815 x^{166} + 66045 x^{167} + 58905 x^{168} + 52360 x^{169} + 46376 x^{170} + 40920 x^{171} + 35960 x^{172} + 31465 x^{173} + 27405 x^{174} + 23751 x^{175} + 20475 x^{176} + 17550 x^{177} + 14950 x^{178} + 12650 x^{179} +10626 x^{180} +8855 x^{181} +7315 x^{182} +5985 x^{183} +4845 x^{184} +3876 x^{185} + 3060 x^{186} + 2380 x^{187} + 1820 x^{188} + 1365 x^{189} + 1001 x^{190} + 715 x^{191} + 495 x^{192} + 330 x^{193} + 210 x^{194} + 126 x^{195} + 70 x^{196} + 35 x^{197} + 15 x^{198} + 5 x^{199} + x^{200})

Y calculando el coeficiente del término 40 del polinomio :

> coeff(expand(F(x)),x,40);

23751 Y razonando de manera análoga al apartado anterior, se podría plantear el

número de soluciones enteras positivas de la ecuación x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 25; ahora solo quedan por repartir 25 objetos, puesto que 15 son fijos (3 por cada caja mínimo).

> binomial(5+25-1,25);

23751

(d) cuando cada caja tiene un número par de objetos.

Este caso es un poco más complejo. Queremos que sólo puedan colocarse en cada caja un número par de bolas. Para ello debemos hacer 0 los términos impares de la función generatriz, lo cual se logra del modo siguiente :

> F := x -> (sum ('x**(2*n)','n'=0..20))^5;

F := x ↦ (∑_{n=0}^{20} x^{2n})^{5}

que si desarrollamos queda :

F (x) := (1 + x^{2} + x^{4} + x^{6} + x^{8} + x^{10} + … + x^{32} + x^{34} + x^{36} + x^{38} + x^{40})^{5}

Si expandimos el polinomio anterior, observamos que no aparecen términos de grado impar : (1 + 5 x^{2} + 15 x^{4} + 35 x^{6} + 70 x^{8} + 126 x^{10} + 210 x^{12} + 330 x^{14} + 495 x^{16} + 715 x^{18} + 1001 x^{20} + 1365 x^{22} + 1820 x^{24} + 2380 x^{26} + 3060 x^{28} + 3876 x^{30} + 4845 x^{32} + 5985 x^{34} + 7315 x^{36} + 8855 x^{38} + 10626 x^{40} + 12645 x^{42} + 14925 x^{44} + 17475 x^{46} + 20300 x^{48} +23401 x^{50} +26775 x^{52} +30415 x^{54} +34310 x^{56} +38445 x^{58} +42801 x^{60} + 47355 x^{62} +52080 x^{64} +56945 x^{66} +61915 x^{68} +66951 x^{70} +72010 x^{72} +77045 x^{74} + 82005 x^{76}+86835 x^{78}+91476 x^{80}+95865 x^{82}+99945 x^{84}+103665 x^{86}+106980 x^{88}+ 109851 x^{90} + 112245 x^{92} + 114135 x^{94} + 115500 x^{96} + 116325 x^{98} + 116601 x^{100} + 116325 x^{102}+115500 x^{104}+114135 x^{106}+112245 x^{108}+109851 x^{110}+106980 x^{112}+ 103665 x^{114} + 99945 x^{116} + 95865 x^{118} + 91476 x^{120} + 86835 x^{122} + 82005 x^{124} + 77045 x^{126} + 72010 x^{128} + 66951 x^{130} + 61915 x^{132} + 56945 x^{134} + 52080 x^{136} + 47355 x^{138} + 42801 x^{140} + 38445 x^{142} + 34310 x^{144} + 30415 x^{146} + 26775 x^{148} + 23401 x^{150} + 20300 x^{152} + 17475 x^{154} + 14925 x^{156} + 12645 x^{158} + 10626 x^{160} + 8855 x^{162} + 7315 x^{164} + 5985 x^{166} + 4845 x^{168} + 3876 x^{170} + 3060 x^{172} + 2380 x^{174} + 1820 x^{176} + 1365 x^{178} + 1001 x^{180} + 715 x^{182} + 495 x^{184} + 330 x^{186} + 210 x^{188} + 126 x^{190} + 70 x^{192} + 35 x^{194} + 15 x^{196} + 5 x^{198} + x^{200})

Y ahora como antes, el coeficiente del término 40 de la función generatriz ...

> coeff(expand(F(x)),x,40);

10626

2 Encontrar el número de soluciones enteras positivas de la siguiente

ecuación:

\underbrace{x + y + z + t}_{n=4} = \underbrace{24}_{k}

Ya he comentado que este problema es equivalente al de los apartados (1a),(1b) y (1c), y su solución combinatoria es :

CR(n, k) = \binom{k + n − 1}{k}

cuando x_{1} + x_{2} + … + x_{n} = k

> binomial(24+4-1,24);

2925

Pero aquí lo que interesa es la aplicación de las funciones generatrices. Aplicando el recíproco de lo dicho en la NOTA 1, el problema de calcular el número de soluciones enteras positivas de la ecuación anterior es equivalente a calcular el número de formas distintas que hay de colocar 24 objetos en 4 cajas con capacidad de 0 a 24 objetos cada una; Es decir, el resultado es el coeficiente del término 24 de la función generatriz:

> F := x -> (sum ('x**n','n'=0..24))^4;

F := x ↦ (∑_{n=0}^{24} x^{n})^{4}

que si desarrollamos

F (x) := (1 + x^{1} + x^{2} + x^{3} + x^{4} + x^{5} + … + x^{20} + x^{21} + x^{22} + x^{23} + x^{24})^{4}

Que si expandimos ... (1 + 4 x + 10 x^{2} + 20 x^{3} + 35 x^{4} + 56 x^{5} + 84 x^{6} + 120 x^{7} + 165 x^{8} + 220 x^{9} + 286 x^{10} + 364 x^{11}+455 x^{12}+560 x^{13}+680 x^{14}+816 x^{15}+969 x^{16}+1140 x^{17}+1330 x^{18}+1540 x^{19}+ 1771 x^{20} +2024 x^{21} +2300 x^{22} +2600 x^{23} + 2925 x^{24} +3272 x^{25} +3638 x^{26} +4020 x^{27} + 4415 x^{28} + 4820 x^{29} + 5232 x^{30} + 5648 x^{31} + 6065 x^{32} + 6480 x^{33} + 6890 x^{34} + 7292 x^{35} + 7683 x^{36} + 8060 x^{37} + 8420 x^{38} + 8760 x^{39} + 9077 x^{40} + 9368 x^{41} + 9630 x^{42} + 9860 x^{43} + 10055 x^{44} + 10212 x^{45} + 10328 x^{46} + 10400 x^{47} + 10425 x^{48} + 10400 x^{49} + 10328 x^{50} + 10212 x^{51}+10055 x^{52}+9860 x^{53}+9630 x^{54}+9368 x^{55}+9077 x^{56}+8760 x^{57}+8420 x^{58}+ 8060 x^{59} + 7683 x^{60} + 7292 x^{61} + 6890 x^{62} + 6480 x^{63} + 6065 x^{64} + 5648 x^{65} + 5232 x^{66} + 4820 x^{67} + 4415 x^{68} + 4020 x^{69} + 3638 x^{70} + 3272 x^{71} + 2925 x^{72} + 2600 x^{73} + 2300 x^{74} + 2024 x^{75} + 1771 x^{76} + 1540 x^{77} + 1330 x^{78} + 1140 x^{79} + 969 x^{80} + 816 x^{81} + 680 x^{82} + 560 x^{83} + 455 x^{84} + 364 x^{85} + 286 x^{86} + 220 x^{87} + 165 x^{88} + 120 x^{89} + 84 x^{90} + 56 x^{91} + 35 x^{92} + 20 x^{93} + 10 x^{94} + 4 x^{95} + x^{96})

Y extrayendo el coeficiente 24 del polinomio anterior obtenemos:

> coeff(expand(F(x)),x,24);

2925

3 Encontrar el coeficiente 50 en (x^{7} + x^{8} + x^{9} + …)^{6}.

En este caso podemos suponer que tenemos 6 urnas con capacidad para 7,8,9, … ∞ objetos; y queremos saber cuántas formas hay de colocar 50 objetos en esas 6 urnas.

F := x ↦ (∑_{k=0}^{∞} x^{k+7})^{6}

es decir

> F := x -> (sum('x**(n+7)','n'=0..infinity))^6;

F := x ↦ \frac{x^{42}}{(x − 1)^{6}}

Si calculamos ahora el coeficiente 50 directamente, no nos da un resultado satisfactorio (pues F no es un polinomio).

> coeff (expand(F(x)),x,50);

coef (\frac{x^{42}}{(x − 1)^{6}} , x, 50)

Pero hay una función propia para el caso de funciones generatrices racionales; y que da como resultado el término n-ésimo de la serie que genera dicha función :

> with (genfunc):
> rgf_term(expand(F(x)),x,50);

1287

Pero podemos analizar detalladamente la función generatriz, para ver que realmente da un número racional (con el sumatorio solamente no somos capaces de apreciarlo). Sabemos que

1 + x + x^{2} + … = (\frac{1}{1 − x})

y por lo tanto, desplazando (multiplicando por x^{7}) ...

x^{7} + x^{8} + x^{9} + … = (\frac{1}{1 − x}) x^{7}

Luego podemos expresar la función generatriz inicial como la siguiente función racional :

G := (\frac{x^{7}}{1 − x})^{6} = \frac{x^{42}}{(x − 1)^{6}}

Ahora, podemos aplicar taylor, y el coeficiente del término 50 es el buscado :

> taylor(expand(G(z)),z=0,60);

(z^{42}+6 z^{43}+21 z^{44}+56 z^{45}+126 z^{46}+252 z^{47}+462 z^{48}+792 z^{49}+ 1287 z^{50}+2002 z^{51}+ 3003 z^{52}+4368 z^{53}+6188 z^{54}+8568 z^{55}+11628 z^{56}+15504 z^{57}+20349 z^{58}+26334 z^{59}+ O (z^{60}))

El coeficiente 50 es 1287, o como antes, aplicando la función especial de la librería genfunc.

4 Probar la igualdad (convolución de Vandermonde):

∑_{k=0}^{n} \binom{r}{k}\binom{s}{n − k} = \binom{r + s}{n}

Comprobar experimentalmente con varios casos y hacer la demostración basándose en la función generatriz de la convolución de (1 + z)^{r} con ella misma.

Comprobación experimental. Atención, n ≤ r + s r, s ≥ 0.

A := (r,s,n) -> sum('binomial(r,k)*(binomial(s,n-k))','k'=0..n);

A := (r, s, n) ↦ \frac{\binom{s}{n}Γ(s − n + 1)Γ(1 + s + r)}{Γ(s + 1)Γ(1 + s + r − n)}

con Γ := z ↦ ∫_{0}^{∞}e^{−t}t^{z−1}dt

B := (r,s,n) -> binomial(r+s,n);

B := (r, s, n) ↦ \binom{r + s}{n}

A(5, 6, 3) = ∑_{k=0}^{3} \binom{5}{k}\binom{6}{3−k} =

\underbrace{\underbrace{\underbrace{\binom{5}{0}}_{1} \underbrace{\binom{6}{3}}_{20}}_{20} + \underbrace{\underbrace{\binom{5}{1}}_{5} \underbrace{\binom{6}{2}}_{15}}_{75} + \underbrace{\underbrace{\binom{5}{2}}_{10} \underbrace{\binom{6}{1}}_{6}}_{60} + \underbrace{\underbrace{\binom{5}{3}}_{10} \underbrace{\binom{6}{0}}_{1}}_{10}}_{165} = \underbrace{\binom{5 + 6}{3}}_{165} = B(5, 6, 3)

A(7, 8, 5) = ∑_{k=0}^{5} \binom{7}{k}\binom{8}{5 − k} = 3003 = \binom{7 + 8}{5}

A continuación se muestra una tabla con algunos valores, que corroboran la igualdad de las expresiones:

> for i from 0 to 2 do
> for j from 0 to 3 do
> for k from 0 to i+j do
> print(i,j,k,A(i,j,k),B(i,j,k));
> od;
> od;
> od;

r s n A(r,s,n) B(r,s,n)
0 0 0  1  1
0 1 0  1  1
0 1 1  1  1
0 2 0  1  1
0 2 1  2  2
0 2 2  1  1
0 3 0  1  1
0 3 1  3  3
0 3 2  3  3
0 3 3  1  1
1 0 0  1  1
1 0 1  1  1
1 1 0  1  1
1 1 1  2  2
1 1 2  1  1

r s n A(r,s,n) B(r,s,n)
1 2 0  1  1
1 2 1  3  3
1 2 2  3  3
1 2 3  1  1
1 3 0  1  1
1 3 1  4  4
1 3 2  6  6
1 3 3  4  4
1 3 4  1  1
2 0 0  1  1
2 0 1  2  2
2 0 2  1  1
2 1 0  1  1
2 1 1  3  3
2 1 2  3  3
2 1 3  1  1
2 2 0  1  1
2 2 1  4  4
2 2 2  6  6
2 2 3  4  4
2 2 4  1  1
2 3 0  1  1
2 3 1  5  5
2 3 2  10  10
2 3 3  10  10
2 3 4  5  5
2 3 5  1  1

Demostración

Sean A(z) y B(z) dos series formales :

A(z) = ∑_{k≥0} a_{k}z^{k}

B(z) = ∑_{k≥0} b_{k}z^{k}

Por el Teorema del binomio de Newton sabemos :

A(z) := (1 + z)^{r} = ∑_{k=0}^{r} \underbrace{\binom{r}{k}}_{a_{k}} z^{k}

B(z) := (1 + z)^{s} = ∑_{k=0}^{s} \underbrace{\binom{s}{k}}_{b_{k}} z^{k}

Multiplicando A(z) por B(z) tenemos (convolución de una serie con ella misma) :

C(z) = A(z)B(z) = (1 + z)^{r}(1 + z)^{s} = (1 + z)^{r+s} = ∑_{k=0}^{r+s} \underbrace{\binom{r + s}{k}}_{c_{k}} z^{k}

Sabemos que el término general del producto de dos series formales viene definido por la operación de convolución

[Z^{n}] (A(z)B(z)) = ∑_{k=0}^{n} a_{k}b_{n−k}

y en nuestro caso particular :

[Z^{n}] (A(z)B(z)) = ∑_{k=0}^{n} \underbrace{\binom{r}{k}}_{a_{k}} \underbrace{\binom{s}{n − k}}_{b_{n−k}} = c_{n}

Luego hemos demostrado la igualdad:

∑_{k=0}^{n} \binom{r}{k}\binom{s}{n − k} = \binom{r + s}{n}

5 Una permutación σ de n elementos se llama desarreglo si no tiene ningún punto fijo (i.e. σ(i) ≠ i ∀i = 1..n.) Denotando D(n) el número de desarreglos de n objetos, demostrar que:

n! = ∑_{k=0}^{n} \binom{n}{k}D(k).

Estudia experimentalmente la relación entre D(n) y n! y trata de establecer y probar la hipótesis correspondiente.

Demostración

Sabemos que P (n) = n! = n(n − 1)(n − 2) ⋯ 1, el número de formas en que podemos “ordenar” n elementos. Si A es un conjunto finito no vacío, una PERMUTACIÓN de A es una biyección de A en A; y se dice que las permutaciones son diferentes si las biyecciones son distintas.

Sean A = a_{1}, a_{2}, ..., a_{n} y σ : A ↦ A una permutación. Sea σ(a_{i}) la imagen de a_{i}, con 1 ≤ i ≤ n. La permutación σ se representa usualmente por

σ = ( \begin{matrix}a_{1} & a_{2} & … & a_{n} \\ σ(a_{1}) & σ(a_{2}) & … & σ(a_{n}) \end{matrix} )

Se puede observar que a cada ordenación de los elementos de A ( a_{σ(1)}, a_{σ(2)}, …, a_{σ(n)}) se le puede asociar una biyección de A definida por σ(a_{i}) = a_{σ(i)}, y recíprocamente a cada biyección σ se le puede asociar la ordenación (σ(a_{1}), σ(a_{2}), …, σ(a_{n})), así las permutaciones pueden considerarse como las ordenaciones de los elementos de A. Una aplicación biyectiva de los elementos de A es lo mismo que dar una ordenación de los elementos de A.

Dentro de todas las permutaciones posibles de n elementos podemos encontrar algunas en las que σ(i) = i, para algún o varios i = 1..n; es decir algunas tendrán puntos fijos. Denotaremos h(n, k) el número de permutaciones de n elementos tales que tengan k puntos fijos.

¿ Y cuánto vale h(n, k) ? Dividimos los elementos en dos partes: una de n-k elementos y la otra de k.

\underbrace{a_{1}, …, a_{n−k}}_{n−k}, \underbrace{a_{n−k+1}, …, a_{n}}_{k}

Y h(n, k) es el número de formas de escoger k puntos fijos entre n elementos (\binom{n}{k}), multiplicado por el número de formas que hay de escoger los n − k restantes de modo que tengan 0 puntos fijos (h(n − k, 0)).

h(n, k) = \binom{n}{k}h(n − k, 0)

y como llamamos desarreglos a las permutaciones que no tienen puntos fijos, denominamos D(n) al número de desarreglos de n elementos; es decir :

D(n) = h(n, 0) ⇒ h(n, k) = \binom{n}{k}D(n − k)

Y si ahora calculamos el número total de formas de ordenar los n elementos, basándonos en la fórmula anterior, resulta ser la suma de todos las formas que hay de ordenar n elementos de modo que tengamos k = 0..n puntos fijos: (suma infinita, considerando los valores negativos nulos)

n! = ∑_{k=0}^{n} h(n, k) = ∑_{k=0}^{n} \binom{n}{k}D(n − k) \overbrace{=}^{r=n−k⇒k=n−r} ∑_{n−r=0}^{n} \underbrace{\binom{n}{n − r}}_{\binom{n}{r}} D(r) =

= ∑_{r=0}^{n} \binom{n}{r}D(r) \overbrace{=}^{r=k} ∑_{k=0}^{n} \binom{n}{k}D(k) = n!

Luego, queda demostrado.

Estudio experimental de la relación D(n) y n!

El estudio experimental estará basado en el procedimiento siguiente, que genera h(n,k) definido antes.

> h := proc(n,m)
         if m = 0 then n!*sum('(-1)^k/k!','k' = 0 .. n)
         else binomial(n,m)*h(n-m,0)
         fi
     end
> D := n -> h(n,0);

D := n ↦ n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!}

> nfac := n -> sum('binomial(n,k)*D(k)','k'=0..n);

nfac := n ↦ ∑_{k=0}^{n} \binom{n}{k}D(k)

> rel := n -> sum('(-1)^k/k!','k'=0..n);

rel := n ↦ ∑_{k=0}^{n} \frac{(−1)^{k}}{k!}

> for i from 0 to 16 do
> print(i,D(i),i!,nfac(i),convert(D(i)/i!,float),convert(rel(i),float));
> od;
> print(infinity,D(infinity),infinity!,D(infinity)/infinity!,rel(infinity));

i  D(i)  i!  nfac(i) =  \frac{D(i)}{i!}  rel(i) =
∑_{k=0}^{i} \binom{i}{k}D(k)  ∑_{k=0}^{i} \frac{(−1)^{k}}{k!}
0  1  1  1  1.  1.
1  0  1  1  0  0
2  1  2  2  .5000000000 .5000000000
3  2  6  6  .3333333333 .3333333333
4  9  24  24  .3750000000 .3750000000
5  44  120  120  .3666666667 .3666666667
6  265  720  720  .3680555556 .3680555556
7  1854  5040  5040  .3678571429 .3678571429
8  14833  40320  40320  .3678819444 .3678819444
9  133496  362880  362880  .3678791887 .3678791887
10  1334961  3628800  3628800  .3678794643 .3678794643
11  14684570  39916800  39916800  .3678794392 .3678794392
12  176214841  479001600  479001600  .3678794413 .3678794413
13 2290792932  6227020800  6227020800  .3678794412 .3678794412
14 32071101049  87178291200  87178291200 .3678794412 .3678794412
15 481066515734 1307674368000 1307674368000 .3678794412 .3678794412
16 7697064251745 20922789888000 20922789888000 .3678794412 .3678794412
⋮  ⋮  ⋮  ⋮  ⋮  ⋮
∞  ∞!e^{−1}  ∞!  ∞!  e^{−1}  e^{−1}

En la página anterior se muestra una tabla con diversos datos. Se pretende estudiar la relación entre D(i) y n!. Por tanto una columna de la tabla muestra algunos D(i) con sus respectivos i!. También puede observarse otra columna, nfact(i), que ofrece la misma apariencia que la de i!. lo cual corrobora la demostración realizada en el paso anterior.

La relación D(i),i! puede apreciarse en la columna \frac{D(i)}{i!}. Se observa que para valores entre 0 … 4 el cociente es variable; pero a partir de 4 … ∞ se estabiliza en e^{−1} = .3678794412.

> convert(exp(-1),float);

.3678794412
Podemos realizar la gráfica de \frac{D(n)}{n!}

> plot ('D(n)/n!',n=0..100);

y observaremos que cuando n → 0 es variable; pero cuando n ≥ 10 se estabiliza en .36 aproximadamente.

Luego, experimentalmente observamos que para n ≥ 4, el 36.788% del número de permutaciones de n objetos es el número de desarreglos de n objetos.

Si volvemos a la tabla, en la última columna están los elementos de la serie con término general ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} ; que coinciden exactamente con la relación \frac{D(n)}{n!}.

> evalb(rel(k)=(D(k)/k!));

true

Y ese es el término general de la serie formal

G(z) = ∑_{n≥0} (∑_{k=0}^{n} \frac{(−1)^{k}}{k!} ) z^{n}

El término general tiende a; mejor dicho es e^{−1} para casi todo n. Parece curioso que ese sumatorio tienda a un número, pero si nos fijamos un poco, cuanto más grande es n, más pequeños son los nuevos sumandos pues como n! crece muy rápido, \frac{1}{n!} para n no demasiado grande es despreciable.

Se puede demostrar que esa serie está generada por la siguiente función :

> G := z -> (exp(-z))/(1-z);

G := z ↦ \frac{e^{−z}}{1 − z}

Luego, si calculamos el desarrollo en serie de Taylor en z=0 de W(z) para sus 20 primeros coeficientes, comprobamos que coinciden con los términos de la serie descritos en la tabla.

> convert(taylor((exp(-z)/(1-z)),z=0,21),float);

(1.0 + 0.5000000000 z^{2} + 0.3333333333 z^{3} + 0.3750000000 z^{4} + 0.3666666667 z^{5} + 0.3680555556 z^{6} + 0.3678571429 z^{7} + 0.3678819444 z^{8} + 0.3678791887 z^{9} + 0.3678794643 z^{10} + 0.3678794392 z^{11} + 0.3678794413 z^{12} + 0.3678794412 z^{13} + 0.3678794412 z^{14} + 0.3678794412 z^{15} + 0.3678794412 z^{16} + 0.3678794412 z^{17} + 0.3678794412 z^{18} + 0.3678794412 z^{19} + 0.3678794412 z^{20} + O (z^{21}))

demostremos que W (z) = \frac{e^{−z}}{1−z} = ∑_{n≥0} (∑_{k=0}^{n} \frac{(−1)^{k}}{k!} ) z^{n}

Sabemos :

secuencia  función generatriz
1, 1, 1, …, 1  A(z) = 1 + z + z^{2} + z^{3} + ⋯ = \frac{1}{1−z}
1, 1, \frac{1}{2}, \frac{1}{6}, …, \frac{1}{n!}, … B(z) = \frac{1}{0!}z^{0}, \frac{1}{1!}z^{1}, \frac{1}{2!}z^{2}, \frac{1}{3!}z^{3}, …, \frac{1}{n!}z^{n}, … = ∑_{n≥0} \frac{1}{n!}z^{n} = e^{z}

Y el término general del producto de dos funciones generatrices AC es ∑_{k=0}^{n} a_{k}c_{n−k}, siendo a_{n}, c_{n} los términos generales de la sucesión generada por las funciones A y C respectivamente.

Y como en este caso a_{n} = 1, ∀n, resulta el término general ∑_{k=0}^{n} c_{n−k} = ∑_{k=0}^{n} c_{k} tenemos :

C(z) = B(−z) = e^{−z} = ∑_{n≥0} \frac{1}{n!}(−z)^{n} = ∑_{n≥0} \underbrace{\frac{(−1)^{n}}{n!}}_{c_{n}} z^{n}

Luego resulta que

[Z^{n}](W (z)) = [Z^{n}] (\frac{e^{−z}}{1 − z} ) = ∑_{k=0}^{n} \frac{(−1)^{k}}{k!}

como queríamos demostrar.

Es el momento de plantear la hipótesis: la relación entre D(i) e i! viene expresada por la siguiente igualdad:

\frac{D(n)}{n!} = ∑_{k=0}^{n} \frac{(−1)^{k}}{k!}

Para ello, partiremos de la fórmula demostrada al principio :

n! = ∑_{k=0}^{n} \binom{n}{k}D(k) \underbrace{=}_{demostrado antes} ∑_{k=0}^{n} \binom{n}{k}D(n − k)

Dividimos los dos miembros por n!

\underbrace{1}_{a_{n}} = ∑_{k=0}^{n} \frac{1}{n!} \underbrace{\binom{n}{k}}_{\frac{n!}{k!(n−k)!}} D(n − k) = ∑_{k=0}^{n} \frac{1}{n!} \frac{n!D(n − k)}{k!(n − k)!} = ∑_{k=0}^{n} \underbrace{\frac{1}{k!}}_{b_{k}} \underbrace{\frac{D(n − k)}{(n − k)!}}_{r_{n−k}}

La fórmula anterior tiene la forma del término general del producto de dos series formales (suma de convolución): [Z^{n}](B(z)R(z)) = [Z^{n}](A(z)) = a_{n} = ∑_{k=0}^{n} b_{k}r_{n−k}, siendo :

A(z) = ∑_{k≥0} a_{k}z^{k} = ∑_{k≥0} 1z^{k} = \frac{1}{1 − z}

B(z) = ∑_{k≥0} b_{k}z^{k} = ∑_{k≥0} \frac{1}{k!}z^{k} = e^{z}

R(z) = ∑_{k≥0} r_{k}z^{k} = ∑_{k≥0} \frac{D(k)}{k!}z^{k}

Luego,

A(z) = B(z)R(z) ⇒ \frac{1}{1 − z} = e^{z}R(z) ⇒ R(z) = \frac{e^{−z}}{1 − z} = W (z)

Y el término general en ambos lados es :

[Z^{n}](W (z)) = \frac{D(n)}{n!} = [Z^{n}] (\frac{e^{−z}}{1 − z} ) \underbrace{=}_{(1)} ∑_{k=0}^{n} \frac{(−1)^{k}}{k!}

(1) demostrado en la página anterior.

Luego la hipótesis queda demostrada y

\frac{D(n)}{n!} = ∑_{k=0}^{n} \frac{(−1)^{k}}{k!}