Logo Studenta
Gratis
179 pág.
Análise combinatória matemática

Vista previa | Página 25 de 30

los 12 libros son indistinguibles entre śı:
tan solo nos interesa de qué color quedarán encuadernados.
Encuadernamos 1 libro en marrón, 1 en rojo y 1 en verde
(cualesquiera de ellos). Nos quedan 9 libros, que podemos
encuadernar en cualquier color. Luego, si denotamos por x1,
x2 y x3 la cantidad final de libros encuadernados en marrón,
rojo y verde, andamos buscando el número de soluciones en-
teras no-negativas de la ecuación
x1 + x2 + x3 = 9,
que de acuerdo a la teoŕıa es igual a (3+9−19 ) = (
11
9 ) = 55.
9.2. Ejercicios del caṕıtulo 2 129
35. Una baraja de naipes.
35a) Selecciones de una carta de cada palo: hay 134 = 28.561.
35b) Selecciones de una carta de cada palo, sin que haya
ningún par igual: [13]4 = 13× 12× 11× 10 = 17.160.
37. Baraja de naipes.
37a) Extracciones de 10 cartas en las cuales habrá al menos
1 as: (5210) − (
48
10) = 9.279.308.324. Al total le restamos las
extracciones en las cuales no hay ases.
37b) Extracciones de 10 cartas en las cuales habrá al exacta-
mente 1 as: 4× (489 ) = 6.708.426.560.
37c) Extracciones de 10 cartas en las cuales habrá al menos
2 ases: (42) (
50
8 ) = 3.221.271.900. El factor (
4
2) cuenta las
selecciones de los 2 ases, mientras que el otro factor cuenta
las selecciones de las 8 cartas restantes.
37d) Extracciones de 10 cartas en las cuales habrá exacta-
mente 2 ases: (42) (
48
8 ) = 2.264.093.964.
39. Número de soluciones enteras de x1 + · · · + xn = m en
las cuales xi ≥ −3, para todo i: de acuerdo a la fórmula del
teorema 10, tendremos un total de
(
n+m+
n veces︷ ︸︸ ︷
3 + 3 + · · ·+ 3−1
n− 1
)
=
(
4n+m− 1
n− 1
)
soluciones.
41. Manzanas y peras. La respuesta al problema es
5!
2! 3!
= 10 formas.
Esta cantidad coincide con el número de permutaciones de las
letras de la palabra MMPPP , donde “M” indica manzana
y “P” indica pera.
130 Caṕıtulo 9. Las soluciones de los ejercicios impares
43. Club deportivo con 30 miembros.
43a) Maneras de seleccionar un equipo de 4 personas: (304 ) =
164.430. Aqúı no interesa el orden entre las personas.
43b) Maneras de seleccionar un equipo de 4 personas, para
participar en la carrera de relevos 100 + 200 + 400 + 800:
ahora interesa cuál persona corre cuál distancia, de forma
que la solución es [30]4 = 30× 29× 28× 27 = 657.720.
45. Grupo de 7 hombres y 4 mujeres.
45a) Selecciones de 6 personas, entre ellas al menos 2 mujeres:
(42) (
7
4) + (
4
3) (
7
3) + (
4
4) (
7
2) = 371 selecciones.
45b) Generalización: en el caso en que hay H hombres, M
mujeres, y hay que seleccionar p personas, de las cuales al
menos h de ellas deben ser hombres y m mujeres, con h+m ≤
p ≤ H + M . La solución es (Mm )(
H
p−m) + (
M
m+1)(
H
p−m−1) +
· · ·+ ( Mp−h)(
H
h ) selecciones.
47. Baile entre 7 mujeres y 10 hombres.
47a) Variantes en las cuales las 7 mujeres participan, con un
acompañante masculino diferente: [10]7 = 604.800.
47b) Mismo asunto que en a), pero tomando en cuenta cuáles
hombres quedaron sin bailar: (103 ) = (
10
7 ) = 120.
47c) Mismo asunto que en 47a), pero si se sabe con certeza
que 2 hombres determinados siempre serán sacados a bailar:
[7]2 × [8]5 = 282.240.
47c) Mismo asunto que en 47b), pero si se sabe con certeza
que 2 hombres determinados siempre serán sacados a bailar:
(83) = (
8
5) = 56.
49. Fiesta escolar con 12 niños y 15 niñas.
49a) Selecciones de 4 parejas para un baile: (124 ) (
15
4 ) =
675.675.
49b) Generalización: cuando hay n niños, m niñas y se deben
seleccionar k ≤ min{n,m} para un baile: (nk ) (
m
k ).
9.2. Ejercicios del caṕıtulo 2 131
51. División de m+ n+ p objetos distinguibles en 3 grupos
con m, n y p objetos en cada grupo, sin distinguir el orden
entre los grupos:(
m+ n+ p
m
) (
n+ p
n
)
maneras.
53. Tenemos n primos distintos p1, . . . , pn. Sea q = pα11 ·
pα22 · · · pαnn , con αi ∈ N.
53a) Número de divisores de q. Primero observamos que la
cantidad de divisores de cada primo pi son 2, mientras que la
cantidad de divisores de pαii son αi +1. Además, la cantidad
de divisores de pi·pj (i 6= j) son (αi+1)·(αj+1). Por lo tanto,
la cantidad de divisores de q es (α1 +1) · (α2 +1) · · · (αn +1).
53b) Suma de los divisores de q. Claramente esta suma es
igual a∑
d|q
d =
∑
0≤βi≤αi
pβ11 · p
β2
2 · · · pβnn
= (1 + p1 + p21 + · · ·+ p
α1
1 ) · · · (1 + pn + p2n + · · ·+ pαnn ).
55. Selecciones de 12 personas de entre 17.
55a) Si dos personas dadas de estas 17 no pueden ser selec-
cionadas juntas: (1712) − (
15
10) = 3.185 selecciones (al total de
selecciones le restamos aquellas en las cuales los fulanos se
encuentran juntos).
55b) Generalización: en el caso de seleccionar n personas
de entre N , con la restricción que k personas espećıficas no
pueden ser seleccionadas juntas, la solución es (Nn )− (
N−k
n−k ).
57. El problema del bote: hay 31 candidatos, de los cuales
10 se pueden sentar en el costado izquierdo, 12 en el costado
derecho y 9 en cualquiera de los costados. Hay que seleccionar
4 de ellos para cada uno de los costados del bote. En total
132 Caṕıtulo 9. Las soluciones de los ejercicios impares
habrá
4∑
k=0
4∑
i=0
(
9
k
)(
12
4− k
)(
9− k
i
)(
10
4− i
)
= 15.638.850
selecciones distintas: primero seleccionamos los k indiferentes
que irán en el costado derecho (0 ≤ k ≤ 4). Esto puede
hacerse de ( 9k ) formas distintas. Para cada selección anterior,
tendremos que completar la tripulación de la parte derecha
con 4−k personas de las 12 disponibles, lo cual puede hacerse
de ( 124−k ) formas. El resto es completamente análogo y no
requiere explicación.
59. El coro con 10 participantes.
59a) Selecciones de 6 participantes durante tres d́ıas, de man-
era que cada d́ıa el coro tenga distinta composición: (106 ) ×
[(106 )− 1]× [(
10
6 )− 2] = [(
10
6 )]3 = 9.129.120.
59b) Generalización: en el caso en que tenemos N partic-
ipantes y son seleccionados n de ellos durante tres d́ıas, la
solución será [(Nn )]3.
61. Palabras de 5 letras que se puede formar a partir de 26
letras distintas.
61a) Si se admiten repeticiones de letras, pero no las repeti-
ciones contiguas: 26 × 25 × 25 × 25 × 25 = 26 × 254 =
10.156.250.
61b) Generalización: mismo asunto, si ahora tenemos N le-
tras distintas y las palabras son de n letras: N(N − 1)n−1.
63. Grupo de 10 parejas de casados, a dividir en 5 grupos
de 4 personas para un paseo en botes.
63a) Número de casos en los cuales un hombre quedará en
el mismo bote que su esposa: (92)(
9
2)(
7
2)(
7
2)(
5
2)(
5
2)(
3
2)(
3
2) =
514.382.400.
9.3. Ejercicios del caṕıtulo 3 133
63b) Número de casos en los cuales dos hombres quedarán en
un solo bote junto con sus esposas: (102 )(
8
2)(
8
2)(
6
2)(
6
2)(
4
2)(
4
2) =
285.768.000. En este caso, el primer factor (102 ) es el número
de maneras de seleccionar las 2 parejas que viajarán juntas
en un bote. El factor (82)(
8
2) es el número de maneras de
seleccionar la tripulación del segundo bote: 2 hombres de
los 8 restantes y 2 mujeres de las 8 restantes. El resto es
análogo.
9.3 Ejercicios del caṕıtulo 3
65. Distribuimos inicialmente 1 bola en cada urna. Quedarán
m − n bolas, a distribuir en las n urnas. Esto es, andamos
buscando el número de soluciones enteras de la ecuación
x1 + x2 + · · ·+ xn = m− n,
con xi ≥ 0, ∀i ∈ {1, . . . , n}. De acuerdo a la teoŕıa, la
solución es (
n+ (m− n)− 1
m− n
)
=
(
m− 1
m− n
)
.
67. Evalúe la suma
∑n
k=3(k − 2)(k − 1)k. Utilizamos la
identidad (k − 2)(k − 1)k = 3! (k3 ), y la fórmula del ejercicio
66f, para obtener:
n∑
k=3
(k − 2)(k − 1)k = 3!
n∑
k=3
(
k
3
)
=
n−3∑
k=0
(
3 + k
3
)
= 3!
(
n+ 1
4
)
=
6(n+ 1)(n)(n− 1)(n− 2)
4!
=
n(n+ 1)(n− 1)(n− 2)
4
.
134 Caṕıtulo 9. Las soluciones de los ejercicios impares
69. Los casos n < k y n = k son triviales y se dejan al lector.
Veamos el caso n > k. En virtud de que la sucesión (mk )m∈N
es estrictamente creciente, entonces existe un único m ∈ N
tal que (
m
k
)
< n ≤
(
m+ 1
k
)
− 1. (9.1)
Luego, al aplicar la identidad indicada, tendremos la sigu-