Análisis CombinatorioUnidad 2. Más estrategias de conteo

Actividad 2. Principio de inclusión-exclusión

1. Encontrar el número de soluciones enteras para la ecuación x1+ x2+x3+x4=19 si−5≤ xi ≤2, ∀1≤ i≤ 4.

( 7+4−17 )= 10 !3 !7 !

=120

Sería igual a x1+ x2+x3+x4=19

x1+5−2+x2+5−2+x3+5−2+ x4+5−2=19

x1+ x2+x3+x4=19−12

x1+ x2+x3+x4=7Buscamos entonces

N ( ͞ c⁻1 c⁻2 c⁻3 c ⁻4)Por simetría:

N (c¿¿1)=N (c¿¿2)=N (c¿¿3)=N (c¿¿ 4)¿¿¿¿

x1+ x2+x3+x4=4

Ya que al sumarle 3 a cualquier x1nos daría 7

Entonces:7 !4 !3 !

=35

Por lo tanto:

∀1≤ i≤ 4.35 paracada ∀1≤ i≤ 4.

Ahora obtenemos N (c¿¿ i c j)¿x1+ x2+x3+x4=1

Ya que al sumarle 3 a x1 y 3 a x2 nos daría 7

Entonces:

Análisis CombinatorioUnidad 2. Más estrategias de conteo

4 !1!3 !

=4

Para cada una de las 4 !2!2 !

=6

Para N (c¿¿ i c j ck)=0¿ pues no hay manera de sumar cuatro números enteros

positivos distintos, tres de ellos mayores que 2 y que sumen 7

Por lo tanto:N ¿

Así que de las 120 ecuaciones enteras no negativas sólo 4 cumplen con las condiciones requeridas.

2. El profesor Grimaldi escribió un examen para su curso de matemáticas para ingeniería. El examen tiene doce preguntas que en total valen 200 puntos. ¿De cuántas formas se pueden asignar el profesor los 200 puntos si cada pregunta debe valer al menos 10 puntos pero no más de 25?

211!12!199 !

=11821414943584528100

x1+x2+ x3+x4+x5+x6+x7+¿ x8+x9+ x10+ x11+ x12=200 para10≤x i ≤25 ¿

x1+x2+ x3+x4+x5+x6+x7+¿ x8+x9+ x10+ x11+ x12=200−(15∗12)¿

x1+x2+ x3+x4+x5+x6+x7+¿ x8+x9+ x10+ x11+ x12=40 ¿

Veamos cuantas preguntas puedenvaler10 puntos20010

=20

Entonces asignamos 12 preguntas que valen 10 y nos quedan 8, ahora hacemos:

19 !12!11!

=75582∗120

20020

=10

21!10!11!

=293930∗200

Análisis CombinatorioUnidad 2. Más estrategias de conteo

20025

=8

19!8 !11!

=75582∗160

11821414943584528100−(75582∗120 )+¿

11821414943584528100−1679115900145320¿1679115900145320 Son las formasen las que se puedenasignar las12

Con las condiciones que nos ponen

i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 i=9 i=10 i=11 i=12

10 1 1 1 1 1 1 1 1 1 1 1 111 1 2 3 4 5 6 7 8 9 10 11 1212 1 3 6 10 15 21 28 36 45 55 66 7813 1 4 10 20 35 56 84 120 165 220 286 36414 1 5 15 35 70 126 210 330 495 715 1001 136515 1 6 21 56 126 252 462 792 1287 2002 3003 436816 1 7 28 84 210 462 924 1716 3003 5005 8008 1237617 1 8 36 120 330 792 1716 3432 6435 11440 19448 3182418 1 9 45 165 495 1287 3003 6435 12870 24310 43758 7558219 1 10 55 220 715 2002 5005 11440 24310 48620 92378 16796020 1 11 66 286 1001 3003 8008 19448 43758 92378 184756 35271621 1 12 78 364 1365 4368 12376 31824 75582 167960 352716 70543222 1 13 91 455 1820 6188 18564 50388 125970 293930 646646 135207823 1 14 105 560 2380 8568 27132 77520 203490 497420 1144066 249614424 1 15 120 680 3060 11628 38760 116280 319770 817190 1961256 445740025 1 16 136 816 3876 15504 54264 170544 490314 1307504 3268760 7726160

De las 709284896615071686, solo 7726160 cumplen la condición de que cada pregunta debe valer al menos 10 puntos pero no más de 25

3. En una florería se deben acomodar quince macetas con flores diferentes en un escaparate de cinco anaqueles ¿De cuántas formas pueden colocarse para que cada anaquel tenga al menos una maceta pero no más de cuatro?

19 !15! 4 !

=3876

xi i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 i=9 i=10 i=11 i=12 i=13 i=14 i=15

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Análisis CombinatorioUnidad 2. Más estrategias de conteo

2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 153 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120

4 1 4 10 20 35 56 84 120 165

220 286 364 455 560 680

De las 3876 maneras de acomodar las flores 15 flores en un escaparate de 5 anaqueles solo 680 cumplen la condición de acomodar de una a 4 en cada uno.

4. Encontrar el número de permutaciones de las 26 letras del alfabeto de modo que no aparezcan los patrones pino, mega, rato ó ten.

26 !=403291461126605635584000000

5. ¿De cuántas formas se pueden colocar los enteros del 1 al 10 en una línea de modo que ningún entero par quede en su posición natural?

6. Sea A={1,2 ,…,7 }. Una función f : A → A tiene un punto fijo si para algún

x∈ A , f ( x )=x .¿Cuántas funciones inyectivas f : A → A tienen al menos un punto

fijo?

7. ¿De cuántas formas se puede diseñar un código secreto asignando a cada letra del alfabeto una letra diferente que la represente?

8. Diez mujeres asisten a un desayuno de negocios. Al entrar, cada una deja en el guardarropa su abrigo y sus portafolios. Al salir, cada una recibe un abrigo y una bolsa al azar,

(a) ¿de cuántas formas se pueden distribuir abrigos y portafolios de manera que ninguna de ellas reciba alguna de sus pertenencias?(b) ¿de cuántas formas se pueden distribuir abrigos y portafolios de manera que ninguna de ellas reciba sus dos pertenencias?