A maior rede de estudos do Brasil

Grátis
179 pág.
Análise combinatória matemática

Pré-visualização | Página 4 de 30

elementos a, b y c esté junto?
2Pueblo y volcán de México.
12 Caṕıtulo 1. Permutaciones
15. En un torneo de gimnasia participan 10 personas. Tres
jueces deben numerarlos, en forma independiente uno de los
otros, en un orden que refleje sus éxitos en el torneo, según
la opinión de cada juez. Se considera ganador el que haya
sido nombrado primero por lo menos por dos jueces. ¿En qué
porcentaje de los casos del torneo se habrá determinado un
ganador?
16. ¿Cuántos collares diferentes se puede confeccionar de
siete cuentas de distinto tamaño (hay que utilizar las 7)?
Generalice el problema para cuando tenemos n cuentas de
distinto tamaño.
17. ¿Cuántos collares diferentes se puede confeccionar de
cinco cuentas iguales y dos de mayor dimensión? Generalice
el problema para cuando tenemos n cuentas de un tipo y m
de otro tipo.
18. Si en una sociedad cada persona es representada por
sus tres iniciales (nombre, primer apellido y segundo apel-
lido), ¿cuántas personas son necesarias para garantizar que
al menos 2 de ellas tienen las mismas iniciales? ¿Y cuántas
son necesarias para garantizar que al menos m de ellas tienen
las mismas iniciales?
19. En un estante hay m+ n libros diferentes, de los cuales
m están encuadernados en negro, y n en rojo. ¿Cuántas per-
mutaciones existen de estos libros, en las que las encuader-
naciones en negro ocupen los primeros m lugares? ¿Cuántas
posiciones hay en las que todos los libros encuadernados en
negro se hallen juntos?
20. ¿De cuántos modos se puede poner 5 anillos diferentes
en los dedos de una mano, omitiendo el pulgar? Generalice
el problema para cuando tenemos n anillos diferentes.
1.6. Ejercicios 13
21. ¿Cuántos brazaletes distintos se puede confeccionar de
cinco esmeraldas iguales, seis rub́ıes iguales y siete zafiros
iguales (en el brazalete deben figurar todas las 18 piedras)?
22. ¿De cuántos modos se puede seleccionar, de las mismas
piedras, tres para un anillo?
23. Para los premios de una olimṕıada matemática se prepararon
3 ejemplares de un libro, 2 de otro y 1 de un tercero. ¿De
cuántos modos se puede entregar los premios, si en la olimṕıada
participaron 20 personas y a nadie se le otorga dos libros de
golpe? Resuelva el mismo problema, bajo el supuesto que a
nadie se le otorgue dos ejemplares de un mismo libro, aunque
se le puede entregar dos o tres libros diferentes.
24. ¿Cuántos números distintos de cuatro cifras se puede
formar a partir de las cifras 0, 1, 2, 3, 4, 5, 6, si cada una de
ellas puede repetirse varias veces?
25. Hallar la cantidad de números de seis cifras, para los
cuales la suma del número formado por las tres primeras
cifras —de estas seis— y del formado por las tres últimas
cifras, sea menor que 1000.
26. Generalice la propiedad 1 (a): Encuentre una fórmula
para la cardinalidad de la unión de tres conjuntos A ∪ B ∪
C, en términos de las cardinalidades de A, B y C y de las
intersecciones de estos conjuntos.
Caṕıtulo 2
Arreglos, distribuciones,
combinaciones y selecciones
2.1 Arreglos en cajas ordenadas
¿Cuántas maneras o arreglos distintos hay de distribuir los
objetos a, b, c en las cajas ordenadas 1 y 2? La respuesta es
24 arreglos distintos, los cuales se enumeran a continuación:
abc | ∅ acb | ∅ bac | ∅ bca | ∅ cab | ∅ cba | ∅
ab | c ba | c ac | b ca | b bc | a cb | a
a | bc a | cb b | ac b | ca c | ab c | ba
∅ | abc ∅ | acb ∅ | bac ∅ | bca ∅ | cab ∅ | cba
Como puede observar el lector, interesa aqúı no solamente
el hecho que las cajas 1 y 2 son ordenadas (por ejemplo, el ar-
reglo “ab | c” es diferente al arreglo “c | ab”), sino que también
interesa el orden de los objetos dentro de cada caja (por ejem-
plo, el arreglo “ab | c” es diferente al arreglo “ba | c”). En
general tendremos . . .
Proposición 8 El número [n]m de maneras de distribuir m
objetos distinguibles en n cajas ordenadas es igual a
[n]m := n (n+ 1) · · · (n+m− 1) = (n+m− 1)!
(n− 1)!
(2.1)
15
16 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
Demostración: En efecto, construyamos primero la tabla
Tm−1 de todos los arreglos de los objetos 1, 2,. . . , m − 1 en
las n cajas ordenadas. Cada arreglo de la tabla Tm−1 es de
forma
i1 i2 · · ·︸ ︷︷ ︸
caja 1
| ik ik+1 · · ·︸ ︷︷ ︸
caja 2
| · · · | · · · im−1︸ ︷︷ ︸
caja n
y puede ser expresado como una secuencia de (m−1)+(n−1)
śımbolos (las m − 1 “letras” ik y las n − 1 rayas verticales
| ). La “letra” m puede ser agregada a esta secuencia de
(m− 1) + (n− 1) + 1 diferentes maneras. Entonces,
|Tm| = (n+m− 1) |Tm−1|
= (n+m− 1) (n+m− 2) · · · (n+ 1) |T1|
= (n+m− 1) (n+m− 2) · · · (n+ 1)n = [n]m,
pues claramente T1 = n.
En el ejemplo anterior tenemos que m = 3, n = 2, siendo
entonces la respuesta igual a [2]3 := 2 · 3 · 4 = 24.
Proposición 9 El número de maneras de distribuir m ob-
jetos distinguibles en n cajas ordenadas, sin que interese el
orden de los objetos dentro de las cajas, es igual a nm.
Demostración: En efecto, cada objeto tendrá n cajas dis-
tintas donde podrá ser colocado, de donde tendremos un total
de nm arreglos, todos distintos.
En el ejemplo anterior, hay 8 = 23 maneras distintas de
distribuir los tres objetos a, b, c, en las 2 cajas ordenadas, si
no interesa el orden de los objetos dentro de las cajas. Estos
8 arreglos son:
abc | ∅ ab | c ac | b bc | a
a | bc b | ac c | ab ∅ | abc
2.2. Palabras en orden creciente 17
2.2 Palabras en orden creciente
Sea A = {a1, a2, . . . , an} un conjunto de n “letras”, orde-
nadas de manera que a1 < a2 < · · · < an. Una “palabra”
x1 x2 · · ·xm de m letras tomadas de A se dice que está en
orden creciente si
x1 ≤ x2 ≤ · · · ≤ xm.
Por ejemplo, sea A = {a, b, c, d}, donde las letras tienen
el siguiente orden: a < b < c < d. ¿Cuántas “palabras” en
orden creciente de 3 letras pueden formarse con las letras de
A? La respuesta es 20 en total. Estas 20 “palabras” son:
aaa abb acc add bbb bcc bdd ccc cdd ddd
aab abc acd bbc bcd ccd
aac abd bbd
aad
Proposición 10 El número de “palabras” en orden creciente
de m letras, tomadas de un conjunto de n letras, es igual a
[n]m
m!
=
(
n+m− 1
m
)
=
(
n+m− 1
n− 1
)
Demostración: En efecto, considere un arreglo de los m
objetos 1, 2, . . . , m en las n cajas ordenadas a1, a2, . . . ,
an, como en la sección anterior. A este arreglo le hacemos
corresponder una “palabra” en orden creciente de la siguiente
forma, explicada primero con un ejemplo:
| 3 |︸ ︷︷ ︸
a1
| 251 |︸ ︷︷ ︸
a2
| |︸ ︷︷ ︸
a3
| 647 |︸ ︷︷ ︸
a4
−→ a1 a2 a2 a2 a4 a4 a4.
La “palabra” en orden creciente se obtiene escribiendo la “le-
tra” a1 tantas veces como el número de objetos dentro de la
caja a1, seguida de la “letra” a2, escrita tantas veces como el
número de objetos dentro de la caja a2, etc.
18 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
Entonces, es claro que para cada arreglo de los m objetos
en las n cajas ordenadas corresponde una y solo una “pal-
abra” en orden creciente. Por otra parte, para cada “palabra”
en orden creciente corresponderán exactamente m! distintas
permutaciones de los m objetos en las n cajas ordenadas.
Luego, en virtud de la proposición 8 del caṕıtulo anterior,
el número total de “palabras” en orden creciente es igual a
[n]m/m!. Por otra parte,
[n]m
m!
=
n(n+ 1) · · · (n+m− 1)
m!
=
(n+m− 1)!
(n− 1)!m!
=
(
n+m− 1
m
)
=
(
n+m− 1
n− 1
)
.
Este tema de las “palabras” en orden creciente tiene una
estrecha conexión con el tema de las combinaciones con reem-
plazo de n objetos, tomando m a la vez, como veremos en la
sección 2.8.
2.3 Número de soluciones de una ecuación
Sea m un entero positivo. ¿De cuántas maneras puede m es-
cribirse como la suma de n sumandos enteros y no-negativos,
tomando en consideración el orden de los factores? Esta-
mos preguntando por el número de soluciones enteras y no-
negativas de la ecuación
x1 + x2 + · · ·+ xn = m, (2.2)
donde xi ∈ N, para cada i ∈ {1, 2, . . . , n}. Otra forma enter-
amente equivalente de enfocar este problema es el siguiente:
¿De cuántas maneras