Download Análisis combinatorio

Análisis
Combinatorio
1
Combinatoria
El arte de contar
“La combinatoria trata, ante
todo, de contar el número de
maneras en que unos objetos
dados pueden organizarse de
una determinada forma.”
Introducción a la combinatoria
Ian Anderson
2
El papiro Rhind:
En 1858 el egiptólogo escocés
A. Henry Rhind compró en
Luxor (Egipto) el papiro que
actualmente se conoce como
papiro Rhind o de Ahmes,
encontrado en las ruinas de un
antiguo edificio de Tebas. Fue
escrito por el escriba Ahmes
aproximadamente en el año
1650 antes de nuestra era.
El papiro mide unos 6 m de largo y 33
cm de ancho. Representa la mejor
fuente de información sobre matemática
egipcia antigua conocida.
Comienza con la frase:
“Cálculo exacto para entrar en
conocimiento de todas las cosas
existentes y de todos los oscuros
secretos y misterios.” 3
El papiro Rhind:
Escrito en hierático, consta de 87 problemas y su resolución.
Nos da información sobre cuestiones aritméticas básicas,
fracciones, cálculo de áreas, volúmenes, progresiones,
repartos proporcionales, reglas de tres, ecuaciones lineales
y trigonometría básica. El problema 79 es de combinatoria.
Veamos una versión “moderna”...
4
La regla del producto
Según iba a St. Ives,
me crucé con un hombre con 7 esposas.
Cada esposa tenía 7 sacos,
cada saco tenía 7 gatos,
cada gato tenía 7 gatitos.
Gatitos, gatos, sacos y esposas.
¿Cuántos iban a St. Ives?
St. Ives Mother Goose
(La mamá oca de San Ives)
5
Estás comiendo en el restaurante de Emile y el camarero le
informa que tiene (a) dos opciones para aperitivos: sopa o jugo;
(b) tres para el plato principal: carne, pescado o un plato de
verduras y (c) dos para el postre: helado o pastel. ¿Cuántas
opciones posibles tienes para tu comida completa?.
El total de posibilidades será: 2
.3 .2
= 12
6
Principio multiplicativo (ilustración gráfica)
a2
a1
b1
c1
b3
b2
c 2 c1
c2
c1 c2
b1
c1
b3
b2
c2 c 1 c 2
c1
c2
El primer elemento puede escogerse de dos
formas distintas: a1 o a2.
El segundo de tres maneras distintas: b1, b2 o b3.
El tercer elemento puede escogerse en dos modos
distintos: c1 o c2.
El total de posibilidades será: 2 x 3 x 2 = 12
7
La regla del producto o principio multiplicativo
Si una elección tiene m alternativas posibles y otra n,
entonces la realización de ambas tiene m x n.
Mozart compuso un vals con 11
posibilidades distintas para 14 de los 16
compases y 2 posibilidades para cada uno
de los restantes. ¿Se habrán llegado a
escuchar alguna vez
todas las
realizaciones posibles?
11
 11

11  2  2  11  2 





14
2
14
1.518.999.334.332.964  1,52  10
15
8
1
4
3
2
6
5
¿Cuántas fotografías
distintas podemos
hacer cambiando a
los personajes de
posición?
¿Cuántas
permutaciones son
posibles?
7
7  6  5  4  3  2 1  5.040
1
2
3
4
5
6
7! 5.040
7
9
Permutaciones (sin repetición)
Dados n objetos distintos, llamamos permutación a una
ordenación particular de los n objetos en una fila.
Ejemplo: Hay 6 posibles permutaciones con las tres letras
a, b, c: abc, acb, bac, bca, cab, cba.
El número de permutaciones de n objetos diferentes tomados
todos a la vez es n! (se lee “n factorial” o “factorial de n”).
Usando la regla del producto: hay n posibles objetos para la
primera plaza de la fila, n-1 objetos posibles para ocupar la
segunda, etc..
Pn  n(n  1)( n  2)x x3x 2x1  n !
10
Con las letras de la palabra DISCO, ¿cuántas palabras distintas
(con o sin sentido) se pueden formar?
Evidentemente, al tratarse de palabras el orden importa.
Tenemos que formar palabras de cinco letras con cinco
elementos: {D, I, S, C, O}, que no están repetidos.
P5  5! 120
El cálculo del número de permutaciones “n!” se cree que apareció por
primera vez en la India. Se tiene constancia de ejemplos del año 300
antes de nuestra era. En el siglo XI la "fórmula general" era bien
conocida en la India y los países árabes.
11
Existencia de infinitos números primos
Podemos encontrar uno de los primeras
aplicaciones del factorial en una prueba de
Euclides de la existencia de infinitos números
primos. Euclides argumentaba que siempre
existe al menos un primo entre n y (n! + 1) de
la siguiente manera:
(a) n! y (n! + 1) no tienen factores comunes.
(b) O bien (n! + 1) es primo o bien es factorizable:
(b.1) Si (n! + 1) es primo queda demostrada la afirmación.
(b.2) Si (n! + 1) puede descomponerse en factores, por (a) ninguno
de ellos puede dividir a n!. De modo que cualquier factor de (n! + 1)
estará entre n y (n! + 1).
(b.2.1) Si el factor es primo queda demostrada la afirmación.
(b.2.2) Si el factor no es primo, entonces por el mismo argumento
(b.2), será mayor que n y podemos volver a descomponerlo hasta
12
encontrar finalmente un primo mayor que n.
Explosión combinatoria
¿Cuál es el número de posibles ordenaciones
de una baraja de póker de 52 cartas?
El resultado es 52!, que es aproximadamente 8 × 1067.
Observa que a partir de una simple baraja obtenemos un
enorme número, superior, por ejemplo, al cuadrado del
número de Avogadro: 6,02 × 1023.
13
Fórmula de Stirling
n! ~ 2  n
1
n
2
e
n
James Stirling presentó su fórmula en
“Methodus Differentialis” publicado
en 1730.
La demostración de la fórmula de Stirling puede encontrarse en la
mayoría de textos de análisis. Vamos a verificar la bondad de la
aproximación usando el programa StirlingApproximations, que
imprime: (a) n!, (b) la aproximación de Stirling y (c) el cociente de
ambos valores. Observemos como ese cociente se acerca a 1 a
medida que n crece. Se dice entonces que la aproximación es
asintótica.
A veces, al resolver un problema de combinatoria, es mejor
encontrar una aproximación asintótica formada por funciones
cuyo comportamiento es fácil de comprender que la solución
exacta, cuyo comportamiento escapa a nuestra intuición.
14
Supongamos que los siete personajes de Star Treck se hacen
fotografías en fila en todas las permutaciones posibles. ¿En
cuántos casos Data y Picard aparecen juntos?
Pensemos que Data y Picard son siameses o que van dentro de un saco. El
número de posibles fotografías sería entonces de: 6! = 720.
Pero además, para cada una de esas fotografías, Data puede estar a la
derecha o a la izquierda de Picard. Luego el resultado es: 2x6! = 1440.
15
Varias personas se sientan a una mesa
redonda. Consideraremos que dos formas de
sentarse coinciden si cada persona tiene los
mismos vecinos en ambos lados. ¿De cuántos
modos diferentes se pueden sentar 4 personas?
¿Y 7? ¿Y n?
(1) La relación de vecindad se conserva en las permutaciones
cíclicas
y en caso de una simetría.
En el caso de 4 personas, tendremos 4 permutaciones
cíclicas y una simetría especular para cada una: 2 x 4 = 8
transformaciones que conserven la relación de vecindad.
16
Permutaciones cíclicas
Espejo
Permutaciones simétricas
Como el número total de permutaciones de 4 personas es
igual a 4! = 24, tendremos 24 / 8 = 3 formas distintas de sentarse.
17
(2) Si hay 7 personas alrededor de la mesa, tendremos
7! / (7 x 2) = 360 modos.
(3) Y, en general, en el caso de n personas:
n! / (n x 2) formas.
18
En una reunión deben intervenir 5 personas: A, B, C, D y E.
¿De cuántas maneras se pueden distribuir en la lista de
oradores, con la condición de que B no debe intervenir
antes que A?
El número total de posibles listas de oradores distintas es 5!.
Podemos asociar a cada permutación del tipo: (...A...B...) la
misma permutando (...B...A...). Esta última no nos vale. De
modo que por cada par hay sólo una manera que satisface la
condición planteada. Tendremos 5! / 2 = 60 maneras.
19
El mismo problema, pero con la condición de que A deba
intervenir inmediatamente antes que B.
Si A interviene inmediatamente antes que B, podemos
considerarlos como si fuesen un solo orador. Es decir,
ahora sólo contamos las permutaciones tipo: ...AB...
Tendremos entonces: 4! = 24 formas.
20
Emparejamientos
Dados 2n objetos distintos, ¿cuántas maneras
hay de formar n parejas?
Intentemos agrupar los 2n objetos usando
n pares de paréntesis: ( , ) ( , ) ( , ) ... ( , )
Hay 2n espacios vacíos y 2n objetos, luego los
podemos colocar de (2n)! maneras distintas.
Pero para cada paréntesis tenemos 2! = 2
ordenaciones posibles que han de contarse como
una sola (dan lugar al mismo par), debemos
dividir entre 2 x 2 x ... x 2 = 2n.
21
El orden en que hemos colocado los paréntesis
tampoco nos importa y como hay n! maneras
distintas de hacerlo, cada emparejamiento
posible ha sido obtenido de hecho n! veces.
Entonces el número de parejas distintas es:
( 2 n )!
n
2 n!
22
Generalicemos el problema: dados m x n objetos,
¿cuántas maneras hay de formar n conjuntos de
m objetos?
Agrupemos los m x n objetos usando n paréntesis:
( , , ... , ) ( , , ... , ) ( , , ... , ) ... (, , ... , )
Hay m x n espacios vacíos y m·n objetos, luego los
podemos colocar de (m x n)! maneras distintas.
Pero para cada paréntesis tenemos m! ordenaciones
posibles que han de contarse como una sola (dan
lugar a la misma m-terna ). Luego hemos de dividir
entre m! x m! x ... x m! = (m!)n.
23
El orden en que hemos colocado los paréntesis
tampoco nos importa y como hay n! maneras
distintas de hacerlo, cada emparejamiento
posible ha sido obtenido de hecho n! veces.
Entonces el número de maneras es:
( m x n )!
n
( m! ) n!
24
Variaciones (sin repetición)
Un comentarista deportivo de fútbol
Argumentaba que, para conseguir el equipo ideal
de entre sus 20 jugadores, un entrenador probara todas
las posibilidades para dar con el 10 ideal (el portero lo
daba por indiscutible). ¿Le daría tiempo en una liga?
20
 19
18
 ...
12

11  670.442.572.800



10 factores
25
Variaciones (sin repetición)
Según la regla del producto, las maneras de escoger r
elementos distintos de entre un total de n según
un determinado orden, será igual al producto de:
Vn ,r  n (n  1)( n  2)...( n  r  1)
Esta expresión se conoce como variaciones de n elementos
tomados de r en r, y se representa por Vn,r.
Habitualmente se expresa como:
n!
n (n  1)( n  2)... 3  2  1
Vn,r 

(n  r)! (n  r )(n  r  1) ... 3  2  1
En el problema
anterior:
V20,10 
20!
20!

 20 19 18  ... 12 11
(20  10)! 10!
26
¿Cuántos números de tres cifras distintas significativas
se pueden formar con las nueve cifras del sistema decimal
1, 2, 3, 4, 5, 6, 7, 8, 9?.¿Y si admitimos el 0?
Al tratarse de números el orden importa y además nos
dice "cifras distintas" luego no pueden repetirse.
V9,3  9  8  7  504
Si admitimos el 0, como primera opción seguimos teniendo
9 números, pero ahora como segundo número podemos usar
también el 0, luego tenemos 9 posibles candidatos...:
9  9  8  648
27
Variaciones con repetición
Raymond Queneau escribió el libro de
poemas llamado “Cent mille milliards de
poèmes”. Una obra de poesía
combinatoria. Constaba de 10 páginas. En
cada página aparecía un soneto. Cada
soneto está formado por 14 versos. Según
Queneau es posible escoger como primer
verso cualquiera de los primeros versos de
los 10 sonetos originales, como segundo
verso, el segundo verso de cualquiera de
los 10 sonetos originales y así
sucesivamente hasta el verso 14. Y el
soneto resultante tiene sentido. ¿Hace
justicia el título al libro?
10

10



10

10


14
14
28
Variaciones con repetición
Según la regla del producto, las maneras de escoger r
elementos de entre un total de n según un determinado
orden, y con la posibilidad de repetir los elementos
en cada elección, son:
r
n · n · n · ...· n  n
Esta expresión se conoce como variaciones con repetición
y se representa como:
VRn,r  n
r
Se lee: “variaciones con repetición de n elementos tomados de r en r”.
29
¿Cuántos números de tres cifras significativas se pueden
formar con las nueve cifras del sistema decimal
1, 2, 3, 4, 5, 6, 7, 8, 9?. ¿Y si admitimos el 0?
Al tratarse de números el orden importa y además nos
dice que las "cifras se pueden repetir”:
VR9,3  9  729
3
Si admitimos el 0, como primera opción seguimos teniendo
9 números. Pero ahora como segundo número podemos usar
también el 0, luego tenemos 10 posibles candidatos e ídem
para el tercero:
9 10 10  900
30
Combinaciones (sin repetición)
¿Cuántas posibles combinados de dos bebidas podemos
hacer con ginebra, vodka y tequila?
Si el orden importara tendríamos 3 · 2 = 6.
Pero en realidad: (g, v) = (v, g), (g, t) = (t, g) y (t, v) = (v, t),
porque el orden no importa. De modo que debemos dividir
entre 2: 6 / 2 = 3.
¿Cuántas posibles combinados de tres bebidas podemos
hacer con ginebra, vodka, tequila y ron?
De nuevo, si el orden importara tendríamos 4 · 3 · 2 = 24.
Pero en realidad: (g, v, t) = (g, t, v) = (v, g, t) = etc...,
porque el orden no importa. De modo que debemos dividir
entre 3!:
24 / 3! = 4.
31
Combinaciones (sin repetición)
¿Cuántas posibles configuraciones de r elementos
podemos construir desde un conjunto de n elementos
diferentes, sin que importe el orden y no sea posible la
repetición?
Si el orden importara tendríamos n x (n-1) x...x (n - r + 1)
posibilidades. Las podemos partir en clases, de forma que
en cada clase estén aquellas configuraciones que sean la
misma salvo el orden. Como hemos escogido r elementos,
cada clase estará formada por las r! formas distintas de
ordenar esos elementos.
n(n  1)...( n  r  1)
n!

r!
r! (n  r )!
32
Este número se conoce como las combinaciones de n
elementos tomados de r en r y se denota por:
n
n!
C  C (n, r )    
 r  r!(n  r )!
r
n
¿Cuántos grupos de 5 alumnos pueden formarse con los 30
alumnos de una clase. (Un grupo es distinto si se diferencia
por lo menos en un alumno)?.
No importa el orden. No puede haber dos alumnos iguales
(no hay clones) en un grupo, luego no hay repetición.
 30 
30!
C (30,5)    
 142. 506
 5  5!(30  5)!
33
¿Cuántas manos distintas pueden darse a 4
jugadores con 5 cartas cada uno y una baraja de
52 cartas? (Intenta primero una respuesta a ojo).
El primer jugador puede recibir C(52, 5) manos distintas.
Una vez el primer jugador tiene su mano el segundo
puede recibir C(47, 5) manos distintas (5 cartas de las 47
restantes). El tercero: C(42, 5) y el cuarto: C(37, 5). Por la
regla del producto tendremos un total de:
52! 47! 42! 37!
C (52,5)C (47,5)C (42,5)C (37,5) 



5!47! 5!42! 5!37! 5!32!
52!

 1.478.262.843.475.644.020.034.240  1,5 x1024
5! 5! 5! 5! 32!
34
¿De cuántas maneras distintas podemos pintar una tira de
cinco casillas, pintando 2 de rojo y 3 de azul?
Respuesta:
Combinaciones de 5 elementos
tomados de 2 en 2. O de 5 elementos
tomados de 3 en 3:
C(5,2) = C(5,3) = 10.
35
Cine
¿Cuántos caminos
distintos podemos
recorrer desde hogar
a cine? (Cada movimiento
debe acercarnos al cine).
Hogar,
dulce hogar
011010111110
Cualquier posible recorrido consiste en 8 movimientos a la
derecha (1) y 4 movimientos hacia arriba (0). La solución es,
por tanto:
12  12  12!
     
 495
 8   4  8! 4!
36
El triángulo de Pascal (o de Tartaglia)
Ejemplo: para generar el 5º elemento en la fila #7,
sumamos el 4º y 5º elemento en la fila #6.
37
Números combinatorios
Fila 5, posición 2:
5
   10
 2
Fila 10, posición 7:
10 
   120
7
38
9 9
      36
 2 7
9!
9!

2!(9  2)! 7!(9  7)!
 n  n 
   

r  n  r
39
 6 6 7

 4

5

5

     
15  6  21
 n  1  n  1  n 

  
   
 r  1  r   r 
Identidad de
Pascal
40
Demostrar la identidad de Pascal:
 n  1  n  1  n 
  
     C (n, r )
C (n  1, r  1)  C (n  1, r )  
 r  1  r   r 
Demostración:
C (n  1, r  1)  C (n  1, r ) 
(n  1)!
(n  1)!


n  r ! r  1! n  r  1! r !
(n  1) !
 nr 
1 

n  r ! r  1! 
r 
(n  1) !
n
n!

 C (n, r )
n  r ! r  1! r n  r ! r!
41
La suma de fila enésima es el
número total de subconjuntos
posibles de un conjunto de n
elementos = 2n
Fila 5:
1  5  10  10  5  1  25  32
 n  n  n
n
n










C
n
,
r







2

 0  1  2
n
r 0
     
 
n
42
Imaginemos una bola cayendo por el triángulo de Pascal.
Cada fila que baja puede caer hacia la derecha o hacia
la izquierda. ¿Cuántos posibles caminos nos llevan a la
posición 2 de la fila 7?
Respuesta:
7
7!
  
 21
 2  2!(7  2)!
¿Por qué?. Imaginemos que la bola va
siempre a la izquierda, 7 veces a la
izquierda. Acabaremos en la posición
0 de la fila 7. Si va 5 veces a la izquierda
y 2 a la derecha, independientemente
del orden en que lo haga, acabará en
la posición 2 de la fila 7.
43
(1) La buena de la señora Evita Gastos pretendía
pasar de largo junto a la máquina de chicles de
bola sin que sus gemelitos se dieran cuenta.
Primer gemelo: ¡Mamá yo quiero un chicle!
Segundo gemelo: ¡Mamá, yo también. Y lo quiero
del mismo color que el de Toñito!
44
La máquina, tiene chicles de bola de color rojo y
verde. Cada chicle cuesta Bs 1. No hay forma de
saber el color de la próxima bola. Si la Sra. Gastos
quiere estar segura de sacar dos bolas iguales,
¿cuántos bolívares tiene que estar dispuesta a gastar?
1
2
3
"El peor de los casos posibles."
45
(2) Supongamos ahora que la máquina contiene
6 bolas rojas, 4 verdes y 5 azules. ¿Cuántas
monedas necesita la señora Evita Gastos para
estar segura de conseguir dos bolas iguales?.
Generaliza a n conjuntos de bolas, donde
cada conjunto es de un color.
1
2
3
4
El peor de los casos posibles.
1
2
n
...
n+1
+1
46
(3) Ahora pasa por delante de la máquina la
señora Notengo Plata con sus trillizos. La máquina
contiene ahora 6 bolas rojas, 4 verdes y 1 azul.
¿Cuántas monedas necesita la señora para estar
segura de conseguir tres bolas iguales?
1
2
3
4
5
6
47
Podríamos haber atacado el problema en forma
bruta. Asignando a cada bola una letra y
examinando cada una de las:
11! 39.916.800
posibles extracciones para
determinar cuál presenta una
secuencia inicial máxima antes
de que aparezcan 3 bolas
idénticas.
La idea “¡ajá!” consiste en
establecer el caso más
“desfavorable”.
¡Ajá!, Martin Gardner
48
Principio del palomar o
de los cajones de Dirichlet
En promedio la cabeza de una persona tiene
alrededor de 150.000 cabellos. ¿Existen dos
personas en Caracas con la misma cantidad de
pelos en la cabeza ?
Peter Gustav Lejeune
El principio del palomar establece que si n
Dirichlet (1805 -1859)
palomas se distribuyen en m palomares y
si n > m, entonces al menos habrá un palomar con más de una
paloma. Por ejemplo: si se toman trece personas, al menos dos
habrán nacido el mismo mes.
El primer enunciado del principio se cree que proviene de
Dirichlet en 1834 con el nombre de Schubfachprinzip ("principio
de los cajones").
49
¿Cuántas palabras distintas (con o sin sentido)
podemos construir utilizando todas las letras de
MISSISSIPPI ?
S = { 1×M, 4×I, 4×S, 2×P }
Llenemos las 11 casillas:
50
S = { 1×M, 4×I, 4×S, 2×P }
•
# de posibilidades para M:
 11 
 
1
 
 10 
 
4
 
´ # de posibilidades para I:
´ # de posibilidades para S:
Multiplicando:
34.650
 6
 
 4
 
´ # de posibilidades para P:
S
I
P M S
I
I
S
I
 2
 
 2
 
S P
51
Permutaciones con repetición
Si n objetos pueden dividirse en r clases con ni
objetos idénticos en cada clase (i = 1, 2, ... , r) es
decir, tal que n1  n2   nr  n.
Entonces el número de permutaciones posibles es:
PR
n!

n1! n2! nr !
con
n1  n2    nr  n
n1 ,n2 ,..., nr
n
¿Por qué? 52
Recuerda el problema de MISSISSIPPI...
 n   n  n1   n  n1  n2   n  n1  n2    nr 1 

   
  
 
n3
nr
 n1   n2  

 
n!
( n  n1 )!
( n  n1  n2 )!



n  n1 ! n1 ! n  n1  n2 ! n2! n  n1  n2  n3 ! n3!
( n  n1  n2      nr 1 )!


( n  n1  n2      nr 1  nr )! nr !



0!1
53
¿De cuántas maneras distintas pueden colocarse
en línea nueve bolas de las que 4 son blancas,
3 amarillas y 2 azules?
El orden importa por ser de distinto color, pero hay
bolas del mismo color (están repetidas y son
indistinguibles) y colocamos 9 bolas en línea y
tenemos 9 bolas para colocar.
4 , 3, 2
9
PR
9!

 1260
4! 3! 2!
54
El binomio de Newton
(a + b)2 = (a + b) (a + b).
Todos los posibles productos son: aa, ab, ba, bb.
(a + b)2 = a2 + 2ab + b2.
(a + b)3 = (a + b) (a + b) (a + b).
Todos los posibles productos son:
aaa, aab, aba, baa, abb, bab, bba, bbb.
(a + b)3 = a3 + 3a2b + 3ab2 + b3.
(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4.
C(4,0) = 1; C(4,1) = 4; C(4,2) = 6; C(4,3) = 4; C(4,4) = 1
55
Teorema del binomio
x  y 
n
n
n j j


  C n, j x y
j 0
 n  n  n  n 1  n  n 2 2
 n  1 n 1  n  n
 x y    y
   x    x y    x y  ...  
0
1 
 2
 n  1
n
n
  1 C n, k   0
Demostrar:
k
k 0
n
0  1   1   C n, k 1
n
k 0
nk
 1
k
n
  C n, k  1
k 0
k
56
Generalización del binomio de Newton
Vamos a encontrar una fórmula similar a la del binomio de
Newton para (a + b + c)n.
Aplicando la propiedad distributiva a:
(a + b + c)n = (a + b + c) (a + b + c) ... (a + b + c)
tendremos todos los posibles productos ah bk cm tales que
h + k + m = n escogidas sobre: S = {n ·a, n · b, n · c}.
De modo que:
(a  b  c) 
n
h k  mn

h,k ,m
n!
h
k
m
a b c
h! k! m!

Coeficientes
Multinomiales
57
Combinaciones con repetición
Queremos pintar r pelotas con n colores. Es como agrupar r
pelotas en n montones, alguno de los cuales puede estar vacíos.
Supongamos n = 4 y r = 5, por ejemplo.
La configuración 1 1 0 1 0 1 0 1 significa: hay tantas bolas
como 1s y 0 = “pasa al siguiente color”. Hay 2 bolas del primer
color, 1 bola del segundo color, 1 bola del tercer color y 1
bola del cuarto color.
¿Qué significa: 1 1 1 1 1 0 0 0 y 0 0 1 1 1 1 1 0?
Siempre hay 5 unos y 3 ceros (cambios de color).
En el caso general, f(n, r) será el número de maneras de
disponer r unos y n-1 ceros en una secuencia que consta
de n – 1 + r símbolos en total.
f(n, r) = # de maneras de escoger n-1 lugares entre n + r – 1 o
58
f(n, r) = # de maneras de escoger r lugares entre n + r – 1
Combinaciones con repetición
¿Cuántas combinaciones con repetición de 2
elementos sobre el conjunto:
S = {×a, ×b, ×c , ×d} son posibles?
Tenemos 4 “colores” (n = 4) y 2 “bolas” (r = 2).
Tenemos 2 1’s y 4–1=3 0’s:
11000 = {a, a}
10100 = {a, b}
10010 = {a, c}
10001 = {a, d}
01100 = {b, b}
01010 = {b, c}
01001 = {b, d}
00110 = {c, c}
00101 = {c, d}
00011 = {d, d}
59
Combinaciones con repetición
Un total de 10 posibilidades:
{a, a}, {a, b}, {a, c}, {a, d}, {b, b},
{b, c}, {b, d}, {c, c}, {c, d}, {d, d}.
60
Combinaciones con repetición
El número de r-combinaciones de un conjunto
con n objetos distintos, cada uno repetido
infinitamente, es:
61
En una confitería hay cinco tipos diferentes de pasteles.
¿De cuántas formas se pueden elegir cuatro pasteles?
No importa el orden (son pasteles). Puede haber
dos o más pasteles repetidos (hasta cuatro), luego se
trata de combinaciones con repetición:
62
La Combinatoria es una rama de la matemética
que estudia colecciones de objetos (normalmente
finitos) que satisfacen ciertos criterios. En
particular si se trata de contarlos estamos frente a
la Combinatoria Enumerativa. Nos hemos
centrado casi exclusivamente en ella porque es
esencial para cálculos elementales de
probabilidad.
Pero existen otras ramas bien desarrolladas: el
diseño combinatorio, la teoría de matroides, la
combinatoria extremal, la optimización
combinatoria o el álgebra combinatoria.
63
Táctica para chuletas (Optimización combinatoria)
El señor Asamantecas tiene un asador pequeño,
donde apenas caben dos chuletas. Su mujer y su
hija Clara se mueren de hambre y están ansiosas
por comer cuanto antes. El problema es asar las
tres chuletas en el mínimo tiempo posible.
Sr. Asamantecas: Vamos a ver, hacen falta 20 minutos
para asar una chuleta por los dos lados, pues cada uno
tarda 10. Como puedo preparar dos chuletas a la vez,
en 20 minutos puedo tener listas dos. La tercera tardará
otros 20 minutos. Así que la comida estará a punto
dentro de 40 minutos.
Clara: ¡Pero papá!. ¡Si puedes hacerlo en mucho menos!
Acaba de ocurrírseme cómo ahorrar 10 minutos.
¿Cuál fue la feliz idea que se le ocurrió a Clara?
64
Chuletas A, B y C.
A1+B1 = 10 min
Esto es un problema típico
A2+C1 = 10 min
de optimización combinatoria
B2+C2 = 10 min
----------------------- en investigación de operaciones.
Total = 30 min
65
Un par de problemas clásicos de optimización
combinatoria más:
(1) ¿Cómo harías para traer de un río
seis litros de agua, si no tienes a tu disposición,
para medir el agua, más que dos recipientes,
uno de cuatro litros y otro de nueve?
(2) Un pastor tiene que pasar un lobo, un conejo y
una col de una orilla de un río a la otra orilla.
Dispone de una barca en la que sólo caben él
y una de las tres cosas anteriores. Si deja solos
al conejo y al lobo, éste se come a aquél;
si deja al conejo con la col, aquél se la come.
¿Cómo debe proceder para llevar las tres
cosas a la orilla opuesta?
66
Ejercicios de
combinatoria
67
¿Cuántos números de 4 dígitos pueden formarse con los
10 números 0, 1, 2, ..., 9 si:
a) se permiten repeticiones,
b) no se permiten repeticiones,
c) el último número debe ser cero y no se permiten repeticiones?
a) El primer número puede ser cualesquiera de los 9 dígitos
(el cero no es significativo como primera cifra). El segundo, tercero
y cuarto número pueden ser siempre cualquiera de los 10.
Por lo tanto habrá: 9x10x10x10 = 9.000 números posibles.
b) El primer número puede cualquiera de los 9 (excepto el cero).
El segundo puede ser cualquiera de los 9 restantes (ahora el cero
se permite). El tercero tendrá 8 posibilidades y el cuarto 7.
Por lo que resultan: 9x9x8x7 = 4.536 números.
68
c) Análogamente a antes, el primer dígito se puede escoger de
9 maneras, el segundo de 9 y el tercero de 8. El cuarto, sin
embargo, solo tiene una posibilidad: el cero. _ _ _ 0
Entonces, por la regla del producto:
Configuraciones posibles = 9x9x8x1 = 648 números.
69
¿De cuántas maneras posibles se pueden sentar 10 personas en
una banca si solamente hay 4 puestos disponibles?
El primer puesto libre puede ocuparse de 10 maneras, luego el
segundo de 9 maneras, el tercero de 8 y el cuarto de 7. El número
de ordenaciones de 10 personas tomadas de 4 a la vez será:
V10, 4  10 x 9 x8 x 7  5040
70
•
Tenemos 6 alumnos de primer curso, 5 de segundo, 4 de tercero,
3 de cuarto, 2 de quinto, 1 de sexto, como candidatos a recibir 5
premios de la Facultad, uno al alumno menos charlatán, otro al
más atento, otro al que tiene mejor letra, otro al que asiste más a
tutorías y otro al que mejor aparca el carro. Suponiendo que
ningún alumno puede recibir más de un premio, se pide: ¿De
cuántas maneras se pueden distribuir los premios?
Solución:
21 candidatos a 5 premios. Como ningún alumno puede recibir más de
un premio, tenemos 21 candidatos para el primer premio, 20 para el
segundo...
En total 21x20x19x18x17=2.441.880 (distribuciones posibles).
71
En una estantería se quieren colocar 4 libros diferentes de
matemática, 6 de física y 2 de química. ¿De cuántas maneras
distintas se pueden colocar si:
a) los libros de cada materia deben quedar juntos,
b) sólo los libros de matemática deben quedar juntos?
a) Por un lado, los libros de matemáticas se pueden colocar de 4!
maneras, los de física de 6! y los de química de 2!. Los tres grupos
de libros se podrán colocar de 3! maneras. Por consiguiente se
obtienen: 4!x6!x2!x3! = 207.360 distintas configuraciones.
b) Si consideramos los 4 libros de matemáticas como si fuesen uno solo,
entonces tenemos 9 libros, que pueden colocarse de 9! maneras. En todas
estas configuraciones los libros de matemáticas estarían juntos. Pero a
su vez, éstos se pueden colocar de 4! maneras, por lo que en total se
obtienen: 9!x4!= 8.709.120 maneras.
72
¿Cuántas permutaciones pueden formarse con las letras
de la palabra BONDAD?
Respuesta: 6!/2! = 360
¿De dónde sale ese 2!?
Supón que para distinguir la D repetida utilizamos una tilde:
BONDAD’
Ahora todas las letras son distintas, luego hay 6!
permutaciones posibles. Pero cada par de permutaciones:
- - - D - D’
- - - D’- D
en realidad son la misma. Por lo tanto debemos dividir por 2 el
número total de permutaciones.
¿Y por qué por 2!?
Piensa que ocurriría si hubiesen tres D.
73
Ahora este es fácil: una generalización del anterior. ¿Cuántas
palabras distintas de 11 letras podemos formar con la palabra
CACATUA?
La palabra CACATUA consta de 7 letras de las cuales sólo hay 4
tipos distinguibles: 2C, 3A, 1T y 1U. Tendremos entonces que
repetir elementos dentro de cada tipo. Por lo tanto se trata de una
permutación con repetición:
7
2 , 3,1,1
PR
7!

2! 3! 1! 1!
74
En una línea están acomodadas cinco canicas rojas, dos blancas y
tres azules. Si las canicas del mismo color no pueden diferenciarse
entre sí, ¿de cuántas maneras diferentes se pueden ordenar?
Por razonar de otra manera, usemos un astuto truco: Supongamos
que la respuesta es N configuraciones distintas. Observa que dada una
de esas configuraciones, si cambiamos bolas del mismo color entre sí,
como son indistinguibles, la configuración se mantiene.
Entonces, multiplicando N por el número de maneras de colocar las
5 canicas rojas entre ellas, las 2 blancas y las 3 azules, es decir:
Nx5!2!3!, obtenemos las posibles configuraciones si se diferencia entre
si todas las bolas. Pero si todas las bolas fuesen diferentes,
el número de configuraciones sería: 10!. Entonces:
(5!2!3!)N = 10! y despejando N tendremos la respuesta:
N = 10!(5!2!3!).
75
¿De cuántas maneras se pueden dividir 10 objetos en dos grupos
que contengan 4 y 6 objetos respectivamente?
Esto es lo mismo que el número de ordenaciones de 10 objetos, de los
cuales 4 son indistinguibles entre sí y los otros 6 también. Se trata
entonces de una permutación con repetición: 10!/(4!6!) = 210.
El problema también equivale a encontrar el número de selecciones de
4 de 10 objetos (o 6 de 10), siendo irrelevante el orden de selección. Se
trata por lo tanto de combinaciones sin repetición:
C10, 4 
 
10
4
10!
10!


 210
4!(10  4)! 4!6!
76
Se necesitan sentar 5 hombres y 4 mujeres en fila, de manera que
las mujeres ocupen los lugares pares. ¿De cuántas maneras
pueden sentarse?
La configuración general pedida será:
HMHMHMHM
Los hombres se pueden sentar de 5! maneras, y las mujeres de 4!.
Cada configuración de los hombres puede darse con cada
configuración de las mujeres. Entonces se tendrán:
Nº maneras = 5!4!= 2.880
77
¿De cuántas maneras posibles se pueden sentar 7 personas
alrededor de una mesa redonda si: a) se pueden sentar en cualquier
lugar, b) 2 personas en particular no se pueden sentar juntas?
a) Empecemos con una persona sentada en
cualquier lugar. Entonces las 6 personas restantes
se pueden sentar de 6! = 720 maneras. Y esta es
la respuesta, puesto que si la persona inicial se
hubiera sentado en cualquier otro sitio, bastaría un
giro para alcanzar alguna de las configuraciones contadas.
b) Consideremos a 2 personas en particular como si fuesen una sola.
Entonces, hay 6 personas en total, que se pueden colocar de 5! maneras.
A parte, las 2 personas que consideramos como si fueran una, pueden
ordenarse de 2! maneras. Por consiguiente, el número de maneras de
organizar a 7 personas con 2 en particular sentadas juntas es:5!x2!=240.
Usando a), las maneras pedidas serán: 730 - 240 = 480 maneras.
78
¿De cuántas maneras se puede formar un comité de 5 personas
a partir de un grupo de 9?
C9,5 

9
5
9!

 126
5!(9  5)!
¿Si quiero alquilar tres películas, ¿cuántas posibilidades tengo si
en el videoclub sólo hay 200 películas?
C200,3 
 
200
3
200!

 1313400
3!(200  3)!
79
Desde un grupo de 5 matemáticos y 7 físicos se quiere formar un
comité de 2 matemáticos y 3 físicos. ¿De cuántas maneras se puede
hacer si:
a) se puede incluir cualquier matemático y cualquier físico,
b) un físico en particular debe estar en el comité y
c) dos matemáticos en particular no pueden pertenecer al comité?
a) Se pueden seleccionar 2 matemáticos de 5 de C(5,2) maneras y a los
3 físicos de C(7,3) maneras. El número total es el producto = 10·35 = 350.
b) Análogamente: los posibles matemáticos coinciden con los de antes:
C(5,2); y los físicos esta vez se cogen 2 de los 6 que quedan: C(6,2).
Por lo tanto, el total será: C(5,2)·C(6,2) = 10·15 = 150.
c) Ahora sólo tendremos dos matemáticos a escoger entre 3: C(3,2).
Los físicos serán como en a). En total tendremos:
80
C(3,2)·C(7,3) = 3·35 = 105.
¿Cuántas ensaladas diferentes puedo hacer con lechuga, tomate,
cebolla, aceitunas y atún?
1ª Forma: Se pueden seleccionar 1 de los 5 ingredientes, 2 de los 5, ...
hasta coger 5 de los 5. El número de ensaladas distintas es: C(5,1) +
+ C(5,2) + C(5,3) + C(5,4) + C(5,5) = 5+10+10+5+1 = 31.
2ª Forma: Cada ingrediente puede tratarse de 2 maneras, se puede
escoger o rechazar. Puesto que cada 2 formas de tratar a un ingrediente
está asociada con las 2 formas de tratar a cada uno de los otros vegetales,
el número de maneras de tratar a los 5 ingredientes es 25. Pero dentro de
las 25 maneras se incluye el caso de no coger ningún ingrediente. Por
lo tanto:
Número de ensaladas = 25- 1 = 31.
81
¿Cuántas palabras de 4 consonantes diferentes y 3 vocales distintas
se pueden formar a partir de 7 consonantes y 5 vocales?
(No hace falta que tengan sentido)
Se pueden seleccionar 4 consonantes diferentes de C(7,4) maneras y
las 3 vocales de C(5,3) maneras. Además, las 7 letras resultantes
(4 consonantes y 3 vocales) pueden ordenarse entre sí de 7! maneras.
Por lo tanto:
# de palabras = C(7,4)xC(5,3)x7! = 35x10x5040 = 1764000
82
83
84
¿De cuántas formas distintas se pueden acertar 9 resultados en una
quiniela futbolística de 15 resultados?
SOLUCIÓN:
15 resultados
1
X
2
(3 valores)
Los 9 resultados acertados se pueden elegir de
distintas.
15 
   5005
9
formas
En cada resultado, las opciones de fallo son 2, por lo que para cada una
de las formas de acierto, los seis resultados se pueden fallar de:
2x2x2x2x2x2 = 26 formas distintas.
15 
En total tendremos   x 26 formas distintas de acertar 9 resultados igual
 
a 320320 formas.  9 
85
86
87
Sigue en la siguiente diapositiva
88
89
Sigue en la siguiente diapositiva
90
91
Se distribuyen 100 sillas auxiliares entre 5 aulas de modo que
las dos mayores reciben, entre las dos, 50 sillas ¿De cuántas
formas distintas se puede hacer el reparto?
SOLUCIÓN:
A y B : aulas mayores.
50 sillas: asignación de las letras A o B a cada una de las 50 sillas.
Como las sillas son iguales no hay orden en esta asignación y cada
distribución es una combinación con repetición de orden 50 con los
elementos A y B.
C
R
2 , 50
 2  50  1  51 
     51
 
 50   50 
Análogamente, las formas de distribuir las otras 50 sillas son:
R
3, 50
C
 3  50  1  52 
     1326
 
 50   2 
y el reparto se puede efectuar de 51·1326= 67626 formas distintas.
92
Un banco tiene que elegir 5 cargos directivos: director,
subdirector, interventor, tesorero y gerente, entre 8 personas, de
las cuales 3 son hombres (A,E,O) y 5 mujeres (X,Y,Z,V,W).
Se pide averiguar de cuántas formas puede hacerse la elección
si:
a) Los hombre A y E no pueden estar juntos en la misma elección.
b) Entran los 3 hombres.
c) Entran 3 mujeres y 2 hombres.
d) Entran al menos 3 mujeres.
SOLUCIÓN:
a)
Contamos las elecciones: - A pero no con E.
- E pero no con A.
- sin A ni E.
Elecciones con A = ( Elecciones con E) : hay que elegir otra 4 de entre
6
6 de  4  = 15 formas distintas. Ahora debemos asignas cargos. Cada
 
asignación de cargos a los directivos elegidos es una permutación de
las cinco personas elegidas. Por tanto, el número de elecciones con A
es:
 6
  x5!  1800
 4
93
Elecciones sin A ni E: de forma análoga
 6
  x5!  720
 5
Por tanto las opciones sin A ni E juntos es:
 6
 6
 6
  x5!  x5!  x5!  4320
 4
 4
 5
b) Si entran los 3 hombres quedan 2 puestos para las 5 mujeres, que se pueden elegir de
 5  maneras. Considerando la asignación de cargos directivos resultan  5  x5!  1200 elecciones posibles.
 
 
 2
 
 2
 3
5
c) Los hombres se eligen de  2  formas y las mujeres de  3  formas. Por tanto el número elecciones en
 
 
este caso es:
 3  5 
   x5!  3600
 2  3 
d) Contamos separadamente cuando entran 3 mujeres, cuando entran cuatro y cuando entran cinco:
 3  5
 3 5 
   x5!   x5!5!  3600  1800  120  5520
 2  3
 1  4 
94
Un equipo de baloncesto dispone de 12 jugadores: 3 bases, 4
aleros y 5 pívots. ¿Cuántos equipos diferentes puede presentar el
entrenador como quinteto titular?. Se recuerda que de forma
simplificada un equipo de baloncesto consta de un base, dos aleros
y dos pívots.
SOLUCIÓN:
Hay que elegir 1 base, 2 aleros y 2 pívots de un total de 3 bases, 4
aleros y 5 pivots, donde el orden no influye en cada uno de los puestos
correspondientes sino las personas en juego.
 3
C3,1     3bases
1
 4
C4, 2     6aleros
 2
5
C5, 2     10 pívots
 2
El entrenador puede presentar:
3x6x10 = 180 equipos o quintetos titulares.
95
Calcular el número de sucesiones que se pueden formar con 3 aes, 5
bes y 8 ces. ¿ Y si no puede haber dos bes consecutivas?. ¿Y si no hay
dos iguales consecutivas?
SOLUCIÓN:
A)
Cada una de las sucesiones sin condiciones adicionales es una permutación
de aaabbbbbcccccccc, por lo que su número es:
3, 5 , 8 ,
16
P
16!

 720720
3!5!8!
Para que las letras b no aparezcan consecutivas, deben colocarse, entre dos
términos de una de las sucesiones de aes y ces. Como hay 11 símbolos en
esas sucesiones el número de huecos donde se pueden colocar las bes es
12. Debemos elegir 5 de estos 12 huecos.
Se puede hacer de
12 
   792 formas distintas.
5
El número de sucesiones es, por tanto :
12  11!
 130680 formas
 
 5  3!8!
96
c) No se permiten letras iguales consecutivas. Fijémonos en la colocación de las ces. El número de
ces es la suma del nº de aes y bes. 2 opciones:
Si c sólo aparece en uno de los extremos:
c-c-c-c-c-c-c-celigiendo 3 huecos de los 8 posibles para colocar las 3 aes, tendremos la sucesión descrita:
El nº de sucesiones de este tipo es2· 8 
 3
 
-
Si c aparece en los 2 extremos, una colocación será:
c- -c-c-c-c-c-c-c
donde en las posiciones – podemos colocar a o b.
El doble hueco - - puede aparecer en 7 posiciones y se puede llenar con ab o con ba, es decir,
se presenta 2·7 posibilidades. Luego hay que elegir dos huecos entre seis para colocar las
restantes aes. En total, el nº de sucesiones en este caso es
 6
2 x 7 x  
 2
El nº de sucesiones sin letras iguales consecutivas es:
 8
 6
2 x   14 x   112  210  332
 3
 2
97
98
99
100