3. ¿Cuántas permutaciones de 3 hay de a, b, c, d?
4. Liste las permutaciones de 3 de a, b, c, d.
5. ¿Cuántas permutaciones hay de 11 objetos diferentes?
6. ¿Cuántas permutaciones de 5 hay de 11 objetos diferentes?
7. ¿De cuántas maneras se puede seleccionar el presidente, vicepresidente
y secretario de un grupo de 11 personas?
secretario y tesorero de un grupo de 12 personas?
9. ¿De cuántas maneras pueden terminar 12 caballos en el orden ganador,
segundo lugar, tercer lugar?
En los ejercicios 10 al 18, determine cuántas cadenas se pueden formar
ordenando las letras ABCDEF sujetas a las condiciones indicadas.
10. Contiene la subcadena ACE
11. Contiene las letras ACE juntas en cualquier orden
12. Contiene las subcadenas DB y AE
13. Contiene ya sea la subcadena AE o la subcadena EA
14. A aparece antes que D. Ejemplos: BCAED, BCADE
15. No contiene las subcadenas AB, CD
16. No contiene las subcadenas AB, BE
17. A aparece antes que C y C aparece antes que E
18. Contiene ya sea la subcadena DB o la subcadena BE
venusinos, si dos marcianos no pueden estar juntos?
20. ¿De cuántas maneras pueden esperar en una fila 5 marcianos, 10
mercurianos y 8 venusinos, si dos marcianos no pueden estar juntos?
21. ¿De cuántas maneras pueden esperar en una fila 5 marcianos y 5
venusinos?
22. ¿De cuántas maneras puede sentarse 5 marcianos y 5 venusinos en
una mesa circular?
23. ¿De cuántas maneras pueden sentarse 5 marcianos y 5 venusinos
en una mesa circular si dos marcianos no se pueden sentar juntos?
24. ¿De cuántas maneras pueden sentarse 5 marcianos y 8 venusinos
en una mesa circular, si dos marcianos no pueden sentarse juntos?
En los ejercicios 25 al 27, sea X = {a, b, c, d}.
25. Calcule el número de combinaciones de 3 de X.
26. Liste las combinaciones de 3 de X.
27. Demuestre la relación entre las permutaciones de 3 y las combinaciones de 3 elementos de X con un dibujo como el de la figura 6.2.4.
28. ¿De cuántas maneras se puede seleccionar un comité de tres entre
un grupo de 11 personas?
29. ¿De cuántas maneras se puede seleccionar un comité de cuatro entre
un grupo de 12 personas?
30. En cierto momento del juego de lotería del estado de Illinois, se
pidió a una persona que escogiera 6 números (en cualquier orden)
entre 44 números. ¿De cuántas maneras puede hacerlo? El estado
estaba considerando cambiar el juego de manera que se pidiera a
una persona elegir 6 números entre 48. ¿De cuántas maneras podría
hacerlo?
Los ejercicios 31 al 36 se refieren a un club cuyos miembros son 6 hombres
y 7 mujeres.
31. ¿De cuántas maneras se puede elegir un comité de 5 personas?
32. ¿De cuántas maneras se puede elegir un comité de 3 hombres y 4
mujeres?
33. ¿De cuántas maneras se puede elegir un comité de 4 personas que
tenga al menos una mujer?
34. ¿De cuántas maneras se puede seleccionar un comité de 4 personas
que incluya al menos un hombre?
35. ¿De cuántas maneras se puede seleccionar un comité de 4 personas
que incluya personas de uno y otro sexo?
36. ¿De cuántas maneras se puede elegir un comité de 4 personas de
manera que Marta y Rodolfo no estén juntos?
37. ¿De cuántas maneras se puede elegir un comité de 4 republicanos,
3 demócratas y 2 independientes entre un grupo de 10 republicanos,
12 demócratas y 4 independientes?
38. ¿Cuántas cadenas de 8 bits contienen exactamente tres ceros?
39. ¿Cuántas cadenas de 8 bits contienen 3 ceros seguidos y 5 unos?
40. ¿Cuántas cadenas de 8 bits contienen al menos 2 ceros seguidos?
En los ejercicios 41 al 49, encuentre el número de manos de póquer de
5 cartas (sin ordenar), seleccionadas de una baraja común de 52 cartas,
que tengan las propiedades indicadas.
41. Contienen 4 ases
43. Contienen sólo espadas
45. Contienen cartas de todos los palos
46. De la forma A2345 del mismo palo
47. Son consecutivas y del mismo palo (suponga que el as tiene la denominación
más baja).
48. Son consecutivas (suponga que el as tiene la denominación más
baja).
49. Contiene 2 de una denominación, 2 de otra y 1 de una tercera denominación
seleccionadas de una baraja común de 52 cartas.
51. ¿Cuántas manos de bridge son todas del mismo palo?
52. ¿Cuántas manos de bridge contienen exactamente 2 palos?
53. ¿Cuántas manos de bridge contienen los 4 ases?
54. ¿Cuántas manos de bridge contienen 5 espadas, 4 corazones, 3 tréboles
y 1 diamante?
55. ¿Cuántas manos de bridge contienen 5 cartas de un palo, 4 de otro,
3 de otro y 1 de otro palo?
56. ¿Cuántas manos de bridge contienen 4 cartas de 3 palos y una carta
del cuarto palo?
57. ¿Cuántas manos de bridge no tienen cartas con cara? (Una carta
con cara es una de 10, J, Q, K, A.)
En los ejercicios 58 al 62, una moneda se lanza 10 veces.
58. ¿Cuántos resultados posibles hay? (Un resultado es una lista de 10
letras H y T que da el resultado de cada tirada. Por ejemplo, el resultado
H H T H T H H H T H
representa 10 tiradas, donde se obtiene cara las dos primeras veces,
cruz la tercera, cara la cuarta, etcétera).
59. ¿Cuántos resultados tienen exactamente tres caras?
60. ¿Cuántos resultados tienen a lo sumo tres caras?
62. ¿Cuántos resultados tienen el mismo número de caras y cruces?
Los ejercicios 63 al 66 se refieren a un cargamento de 50 microprocesadores,
de los cuales 4 son defectuosos.
63. ¿De cuántas maneras se puede seleccionar un conjunto de cuatro
microprocesadores?
64. ¿De cuántas maneras se puede seleccionar un conjunto de cuatro
microprocesadores no defectuosos?
65. ¿De cuántas maneras se puede seleccionar un conjunto de cuatro
microprocesadores que contenga exactamente dos defectuosos?
66. ¿De cuántas maneras se puede elegir un conjunto de cuatro microprocesadores
que contenga al menos uno defectuoso?
67. Demuestre que el número de cadenas de bits de longitud n ≥ 4 que
contienen exactamente dos ocurrencias de 10 es C(n + 1, 5).
68 Demuestre que el número de cadenas de n bits que tienen exactamente
k ceros sin que haya dos consecutivos es C(n − k + 1, k).
69. Demuestre que el producto de cualquier entero positivo y sus k −
1 sucesores es divisible entre k!.
70. Demuestre que existen (2n − 1)(2n − 3) · · · 3 · 1 maneras de elegir
n pares entre 2n objetos distintos.
Los ejercicios 71 al 73 se refieren a una elección en la que dos candidatos,
Ramírez y Uribe, pretenden el puesto de contralor. Después de
tabular cada voto, Ramírez nunca estuvo atrás de Uribe. Este problema
se conoce como el problema de la urna.
71. Suponga que cada candidato recibe exactamente r votos. Demuestre
que el número de maneras en que pueden contarse los votos es
Cr, el r-ésimo número de Catalan.
72. Suponga que Ramírez recibió justo r votos y Uribe recibió justo u
votos, r ≥ u > 0. Demuestre que el número de maneras en que
pueden contarse los votos es C(r + u, r) − C(r + u, r + 1).
73. Demuestre que si se recibieron exactamente n votos, el número de
maneras de contar los votos es C(n, ⎡n/2⎤ ).
74. Suponga que comenzamos en el origen del plano xy y damos n pasos
unitarios (es decir, cada paso es de longitud uno), donde cada
paso es vertical (arriba o abajo) u horizontal (derecha o izquierda).
¿Cuántas trayectorias de este tipo nunca pasan estrictamente abajo
del eje x?
75. Suponga que comenzamos en el origen del plano xy y damos n pasos
unitarios (es decir, cada paso es de longitud uno), donde cada
paso es vertical (arriba o abajo) u horizontal (derecha o izquierda).
¿Cuántas trayectorias de este tipo se quedan en el primer cuadrante
(x ≥ 0, y ≥ 0)?
76. Demuestre que el número de maneras en que 2n personas, sentadas
alrededor de una mesa circular, pueden saludarse por pares sin
que se crucen los brazos es Cn, el n-ésimo número de Catalan.
77. Demuestre que la instrucción de imprimir en el seudocódigo
for i1
= 1 to n
for i2
= 1 to mín(i1, n − 1)
for i3
= 1 to mín(i2, n − 2)
· · ·
for in—1
= 1 to mín(in—2, 2)
for in
= 1 to 1
println(i1, i2, . . . , in)
se ejecuta Cn veces, donde Cn es el n-ésimo número de Catalan.
78. Suponga que se tienen n objetos, r diferentes y n − r idénticos. Dé
otra derivación de la fórmula
P(n, r) = r! C(n, r)
contando el número de ordenamientos de los n objetos de dos maneras:
■ Contando los ordenamientos al elegir primero las posiciones
para los r objetos distintos.
■ Contando los ordenamientos al elegir primero las posiciones
para los n − r objetos idénticos.
79. ¿Qué está mal en el siguiente argumento, que pretende demostrar
que 4C(39, 13) manos de bridge contienen tres palos o menos?
Existen C(39, 13) manos que contienen sólo tréboles, diamantes
y espadas. De hecho, para cualesquiera tres palos, existen
C(39, 13) manos que contienen sólo esos tres palos. Como hay
cuatro combinaciones de 3 de los palos, la respuesta es 4C(39, 13).
que hay 134 · 48 manos de póquer (sin ordenar) de 5 cartas que
contienen cartas de todos los palos?
Seleccione una carta de cada palo. Esto se puede hacer de
13 · 13 · 13 · 13 = 134 maneras. Como la quinta carta se puede
elegir de 48 maneras, la respuesta es 134 · 48.
81. Sea sn,k el número de maneras en que n personas se pueden sentar
alrededor de k mesas redondas, con al menos una persona en cada
mesa. (Los números sn,k se llaman números de Stirling del primer
tipo). El orden de las mesas no se toma en cuenta. El arreglo de lugares
en una mesa sí se toma en cuenta excepto por las rotaciones.
Ejemplos: El siguiente par no es diferente:
El siguiente par es diferente:
a) Demuestre que sn,k= 0 si k > n.
b) Demuestre que sn,n= 1 para toda n ≥ 1.
c) Demuestre que sn,1= (n − 1)! para toda n ≥ 1.
d) Demuestre que sn,n−1= C(n, 2) para toda n ≥ 2.
e) Demuestre que
para toda n ≥ 2.
f) Demuestre que
g) Encuentre una fórmula para sn,n–2, n ≥ 3 y pruébela.
82. Sea Sn,k el número de maneras para hacer una partición de un conjunto
de n elementos en exactamente k subconjuntos no vacíos. El
orden de los subconjuntos no se toma en cuenta. (Los números Sn,k
se conocen como números de Stirling del segundo tipo.)
a) Demuestre que Sn,k= 0 si k > n.
b) Demuestre que Sn,n= 1 para toda n ≥ 1.
c) Demuestre que Sn,1= 1 para toda n ≥ 1.
d) Demuestre que S3,2= 3.
e) Demuestre que S4,2= 7.
f) Demuestre que S4,3= 6.
g) Demuestre que Sn,2= 2 n–1 − 1 para toda n ≥ 2.
h) Demuestre que Sn,n–1= C(n, 2) para toda n ≥ 2.
i) Encuentre una fórmula para Sn,n–2, n ≥ 3, y pruébela.
83. Demuestre que existen
relaciones de equivalencia en un conjunto de n elementos. [Los
números Sn,k son los números de Stirling del segundo tipo (vea el
ejercicio 82)].
