School Work, combinaciones, y permutaciones">
Teoria Combinatoria - Arvelo PDF
Teoria Combinatoria - Arvelo PDF
Teoria Combinatoria - Arvelo PDF
Estudios realizados:
Ingeniero Industrial. UCAB Caracas 1968
Máster en Estadística Matemática CIENES, Universidad de Chile 1972
Cursos de Especialización en Estadística No Paramétrica Universidad de Michigan
1982
Doctorado en Gestión Tecnológica: Universidad Politécnica de Madrid 2006 (Tesis
Pendiente)
Otras publicaciones del Prof. Arvelo pueden ser bajadas de su página web:
www.arvelo.com.ve , en la sección PDFS.
1
Teoría Combinatoria
Angel Francisco Arvelo L.
TEORIA COMBINATORIA
Entre los requisitos matemáticos más importantes para poder enfrentar con éxito el
cálculo de probabilidades, figuran el análisis combinatorio y el álgebra de conjuntos,
y por tal motivo, el autor ha considerado conveniente desarrollar estos temas, ya
que según su experiencia, muchas de las dificultades que posteriormente se
presentan en el estudio del cálculo de probabilidades, son consecuencia de
deficiencias en alguno de estos dos temas.
El análisis combinatorio tiene por objetivo calcular mediante fórmulas y expresiones
analíticas, el número de arreglos diferentes que se pueden hacer con una colección
de objetos.
La nomenclatura que se utiliza es la siguiente:
Se llama universo al conjunto de elementos de donde se pueden seleccionar
algunos de ellos para formar el arreglo.
m = números de elementos en ese universo.
Así por ejemplo, si en una caja se tiene tres fichas blancas, 4 cuatro negras y dos
rojas, entonces m = 3 + 4 +2 = 9 fichas.
n = número de elementos que se seleccionan del universo para formar el arreglo.
Si de la caja anterior se seleccionan tres fichas, entonces n = 3.
Es evidente que si un mismo elemento no puede intervenir más de una vez en el
arreglo, entonces n m, pero si se permite la repetición, entonces “n” puede ser
mayor que “m”.
El análisis combinatorio, distingue tres tipos fundamentales de arreglos, según se
haga o no distinción en el orden de colocación de los elementos que lo integran.
Estos tres tipos de arreglos serán estudiados de inmediato, y se denominan
combinaciones, variaciones y permutaciones.
Cm,n
m
FG IJ
m!
n H K
n! (m n)!
La expresión Cm,n se lee como combinaciones de “m” en “n”; mientras que “!” se
lee como “factorial” de ese número natural, y se calcula como el producto de todos
los números naturales desde él en forma descendente hasta llegar a “1 “ , a
excepción de 0! = 1
En el ejemplo 1, si se quisiera calcular las combinaciones que se pueden hacer con
estos cinco elementos seleccionando tres, y sin necesidad de hacer la lista,
tendríamos: C5,3
5
FG IJ5!
5 4 3 2 1
= 10 combinaciones.
3 HK
3! (5 3)! 3 2 1 2 1
La expresión
FG mIJ se lee como numero combinatorio de “m” en “n”.
Hn K
Propiedades de los números combinatorios: A continuación se enumeran
algunas de ellas, dejando al lector su demostración matemática:
1°)
FG IJ FG
m
m IJ
; esta propiedad se conoce como “propiedad de complemento”,
nH K H mn K
y resulta obvia, pues por cada combinación de los elementos que intervienen en el
arreglo, existe otra entre los elementos que no intervienen.
2°)
FG mIJ FGm 1IJ FG m 1IJ ; esta propiedad se conoce como “Propiedad de Steefel”,
Hn K Hn 1 K H n K
y establece que el total de combinaciones se descompone en dos; combinaciones
mientras que
4 FG IJ
representa las combinaciones donde no interviene “a”, él queda
3 HK
excluido y quedan 4 para seleccionar 3.
3
Teoría Combinatoria
Angel Francisco Arvelo L.
3°)
FGm m IJ FGm IJ FGm IJ FGm IJ FG m IJ FGm IJ FG m IJ FGm IJ FGm IJ ; RSm n
1 2 1 2 1 2 1 2 1 2 1
H n K H 0 K H n K H 1 K H n 1K H 2 K H n 2K H n K H 0 K Tm n 2
4°)
FG nIJ FGnIJ FGnIJ FGnIJ = 2n
H 0K H1K H 2K HnK
Esta propiedad establece que un conjunto con “n” elementos, tiene 2n subconjuntos,
que son en primer lugar el vacío para el cual se seleccionan 0 elementos, los
conjuntos unitarios con tan solo un elemento, y así sucesivamente hasta llegar al
propio conjunto que también es subconjunto de sí mismo.
Cabe destacar que este conjunto de todos los subconjuntos, es el que se denomina
“Conjunto de Partes”, o también “Conjunto Potencia”, se designa por ℘(𝑆), y más
adelante jugará un papel muy importante, cuando estudiemos las particiones de un
conjunto, que dan lugar a los llamados “Números de Stirling” del segundo tipo.
Por ejemplo: Sea S = {a, b, c}; entonces
℘(𝑆) ={Φ,{a}, {b} ,{c } ,{a,b},{a,c} ,{b,c} ,{a,b.c}} ,el cual tiene 23 = 8 subconjuntos,
que son sus elementos
5°)
FGnIJ FGnIJ FGnIJ FGnIJ FGnIJ FGnIJ = 2 n-1
H 0K H 2K H 4K H1K H 3K H 5K
Estas dos últimas propiedades pueden ser fácilmente deducidas a partir del binomio
de Newton:
𝑛 𝑛 𝑛 𝑛
(𝑎 + 𝑏)𝑛 = ( ) 𝑎𝑛 𝑏𝑜 + ( ) 𝑎𝑛−1 𝑏1 + ( ) 𝑎𝑛−2 𝑏2 + ⋯+( ) 𝑎0 𝑏𝑛
0 1 2 𝑛
Haciendo a=b=1 se obtiene la propiedad 4º) , y haciendo a=1 , b= -1 la 5º)
Ejemplo 2: Si a los elementos del Ejemplo 1 se les permite intervenir más de una
vez para formar la combinación de a 3, habría que añadir a la lista, las siguientes
combinaciones:
aab, aac, aad , aae , bba, bbc, bbd, bbe , cca, ccb, ccd, cce
dda, ddb, ddc, dde, eea, eeb, eec, eed, aaa, bbb, ccc, ddd, eee.
4
Teoría Combinatoria
Angel Francisco Arvelo L.
y a las 10 combinaciones anteriores, habría que sumarle estas nuevas 25 , para un
total de 35 combinaciones diferentes.
El análisis combinatorio también proporciona una fórmula matemática para calcular
el número de combinaciones con repetición, sin necesidad de hacer la lista, y según
la cual: Cm' ,n
FG
m n 1 IJ; donde Cm' ,n representa el número de combinaciones
n H K
con repetición de “m” elementos seleccionando “n”.
C7' ,2
FG
7 2 1
8IJ FG IJ
= 28
H 2 2 K HK
En el caso del dominó cubano, que va desde el 0 hasta el 9, el número de piedras
es: '
C10 ,2
FG
10 2 1 IJ FG IJ
11
= 55
H 2 K H K
2
Ejemplo 5: Con los elementos del ejemplo 4, definir todas las variaciones con
repetición que pueden formarse, seleccionando dos de ellos.
Solución: A las doce anteriores hay que añadir las siguientes cuatro: aa, bb, cc, dd
para un total de dieciséis variaciones diferentes.
Ejemplo 6: Con los elementos del universo {a, b, c, d}, definir todas las
permutaciones posibles.
Solución: Por ser una permutación se seleccionan todos, y el orden de colocación
diferencia a un arreglo de otro, por lo tanto, sus permutaciones son:
abcd , abdc ,acbd , acdb , adbc , adcb , badc, bacd , bcad, bcda, bdac, bdca
cabd, cadb, cbad , cbda , cdab ,cdba , dabc, dadc , dbac ,dbca, dcab, dcba
2°) Cuando k=2 , es decir cuando en el universo sólo hay dos tipos de elementos,
entonces se tiene : n1 + n2 = n , y se obtiene:
Pn;n1,n2
FG
n
IJn!
n! FG IJ FG IJ
n
n
Cn,n1 Cn,n2
H
n1,n2 K
n1 ! n2 ! n1 !(n n1)!H K H K
n1 n2
En este caso, la permutación queda definida al seleccionar los n 1 puestos que le
corresponden a los elementos del tipo 1, y en los n-n1 restantes van los del tipo 2
Ejemplo 8: Con los elementos del universo {a, a, a, b, b}, definir todas las
permutaciones posibles.
Solución: Este es un caso de una permutación con repetición, donde en el universo
sólo hay dos tipos de elementos “a” y b”. Las permutaciones posibles son: aaabb,
aabab , aabba , abaab, ababa , abbaa, baaab, baaba,babaa, bbaaa.
La permutación también quedaría definida señalando los tres puestos ocupados por
las “a” es decir: 123, 124 , 125, 134 , 135, 145, 234, 235, 245 y 345 .
P5;3,2
FG IJ
5
5! FG IJ FG IJ
5
5
10
H K
3,2 3! 2! HK HK
3 2
Ejemplo 9: Una persona posee dos pares de zapatos, tres pantalones y cinco
camisas. ¿De cuantas maneras diferentes se puede vestir?
Solución: La persona debe seleccionar una prenda de cada tipo para vestirse, y si
se cambia por lo menos una de las ella, está vestido de diferente manera.
El total de formas como puede vestirse es: 2 x 3 x 5 = 30
Ejemplo 10: Para ir de una ciudad a otra, una persona puede hacerlo en autobús,
en tren o en avión, y existen tres rutas de autobús, dos vuelos y cinco itinerarios
de tren. ¿De cuantas formas diferentes puede viajar?
Solución: Las alternativas son excluyentes, pues si elige una quedan descartadas
las otras. El total de maneras es entonces: 3 + 2 + 5 = 10.
miembros. C12,4
FG IJ
12
12!
495
H K
4 4! 8!
b) Al existir jerarquía se trata de una variación, pues aunque los miembros sean
los mismos, la comisión es diferente si están en diferentes cargos.
12!
V12,4 11880
8!
c) En esta tercera situación, es necesario aplicar un razonamiento muy frecuente
en combinatoria, que es seleccionar primero y ordenar después.
Existen 495 formas de seleccionar a los cuatro miembros de la comisión (caso a)
sin distinguir cargos, y una vez seleccionados los miembros, ellos pueden
permutarse en los cargos.
8
Teoría Combinatoria
Angel Francisco Arvelo L.
Como el cargo de vocal está repetido dos veces, se trata de una permutación con
repetición, y de allí que el total de maneras como cuatro miembros pueden
4!
asignarse los cargos es: P4;11, ,2 12 .
1!1! 2!
Aplicando el principio multiplicativo, el total de comisiones diferentes es por lo
tanto: 495 x 12 = 5940.
Nótese que este mismo razonamiento se hubiese podido aplicar en b), pero
multiplicando por 4! = 24 pues allí los cuatro cargos son diferentes, y se trata de
una permutación sin repetición. En general: Vm,n = Cm,n x n!
Ejemplo 12: Un grupo de nueve personas está conformado por tres matrimonios y un
hijo de cada uno de ellos. ¿De cuantas maneras distintas pueden fotografiarse
formando una sola fila, con la condición de que cada hijo aparezca entre sus dos
padres?
Solución: Cada matrimonio pude acomodarse de dos maneras, con el padre a la
izquierda del hijo y la madre a su derecha, o viceversa, y también los tres matrimonios
pueden permutarse de 3! = 6 formas distintas.
Aplicando el principio multiplicativo, el total de formas como pueden fotografiarse es:
23 x 6 = 48 formas
Ejemplo 13: ¿De cuantas maneras distintas pueden repartirse diez regalos distintos
entre tres personas, con la condición de que cada persona reciba por lo menos dos
regalos? .
Solución: Existen cuatro procedimientos excluyentes para repartir los diez regalos,
que son: 6+2+2 ó 5+3+2 ó 4+4+2 ó 4+3+3.
Los regalos son distintos, por lo tanto distinguibles asignándoles números 1,2…10
Supongamos que las tres personas son A , B y C.
El caso 6+2+2 equivale a permutar 6 A´s, 2 B´s y 2 C´s en 10 lugares
Por ejemplo el reparto AAAAAABBCC significa que los primeros seis regalos son
para A, el 7 y el 8 para B, y el 9 y 10 para C.
10!
El total de permutaciones en este caso son:
6!2!2!
Pero no necesariamente A puede ser la persona que recibe 6 regalos; puede serlo
también B o C
10 !
Con el procedimiento 6+2+2 las formas son: 3 x = 3780
6 ! 2! 2!
Aplicando este mismo razonamiento en los otros casos:
10 !
Con el procedimiento 5+3+2 las formas son: 3! x = 15120
5 ! 3 ! 2!
10 !
Con el procedimiento 4+4+2 las formas son: 3 x = 9450
4 ! 4 ! 2!
10 !
Con el procedimiento 4+3+3 las formas son: 3 x = 12600
4! 3! 3!
9
Teoría Combinatoria
Angel Francisco Arvelo L.
Los casos son excluyentes, por lo que se puede aplicar el principio aditivo, y de allí
que el total de repartos diferentes es:
3780 + 15120 + 9450 + 12600 = 40950
Ejemplo 14 En una elección participan tres candidatos, y hay doce electores. Cada
uno de los electores vota por uno y por sólo un candidato.
¿De cuantas maneras diferentes puede ser el escrutinio?
Solución: Se trata de una combinación con repetición, pues al hacer el escrutinio lo
que interesa es el número de votos a favor de cada candidato, y no el orden en que
fueron emitidos
Si los candidatos son A, B y C, el escrutinio por ejemplo AAAAAABBBBCC es idéntico
al AABBACAABACB, pues en ambos “A” obtiene 6 votos, B cuatro y C dos.
Se seleccionan 3 elementos del universo {A, B, C} para colocarlos con repetición, en
doce posiciones, que representan el voto de cada elector.
Lo que importa es el escrutinio, y no el orden en que fueron emitidos los votos; y de
Ejemplo 15 Con los dígitos {0,1,2,3,4,5,6} , ¿cuántos números pares de cuatro cifras
sin dígitos repetidos, se pueden formar ?.
Solución: Para que el número sea par, debe terminar en 0, 2, 4 ó 6 , y para que se
considere de cuatro cifras no puede comenzar por 0.
Hay que considerar dos casos excluyentes:
Caso 1: Pares que terminan en 0.
En este caso quedan disponibles todos los otros seis dígitos para ocupar las tres
primeras posiciones, y se trata de una variación pues el orden de colocación de los
dígitos diferencia a un número de otro.
El total de números es este caso es: V6,3= 6 x 5 x 4 = 120
Caso 2: Pares que terminan en 2,4 ó 6
En este caso hay que restar de las V6,3 = 120 , los que empiezan por cero, que
son:V5,2= 5 x 4 = 20 , debido a que quedan disponibles cinco dígitos para ocupar la
segunda y tercera posición.
El total de números es este caso es: 3 x (120-20) = 300
Aplicando principio aditivo, encontramos que el total de números pares de cuatro
cifras que pueden formarse es: 120 + 300 = 420
Ejemplo 16: Una flauta tiene cuatro agujeros, cada una de las cuales puede ser o
no tapado con los dedos de la mano, emitiendo un sonido diferente.
¿Cuántos sonidos diferentes puede emitir la flauta?
Solución: Existe la alternativa de no tapar ninguno de los agujeros, o tapar uno, o
tapar dos, etc., hasta tapar los cuatro.
Ejemplo 18: Entre seis oficiales y quince soldados hay que formar una patrulla de
ocho, que debe estar compuesta por dos oficiales, uno de los cuales la dirigirá, y
por seis soldados. ¿Cuántas patrullas diferentes se pueden formar?
Solución: Las formas de elegir a los oficiales representa una variación, mientras que
las de elegir a los soldados una combinación.
Ejemplo 19: En una carrera de caballos intervienen diez ejemplares, entre los que
figuran A, B y C.
¿De cuantas formas posibles pueden llegar los diez ejemplares a la meta, con la
condición de que “A” le gane a “B”, y éste a su vez a “C”?
Solución: El orden de llegada de los diez ejemplares puede ser de 10! formas , y el
de los ejemplares A, B y C de 3! = 6 formas
De estas 6 formas, sólo en una ellas “A” le gana a “B” y éste a “C” que es ABC.
10 !
Total de formas = = 604800.
6
Ejemplo 21: La junta directiva de una empresa tiene cinco cargos, presidente,
secretario, tesorero y dos vocales.
11
Teoría Combinatoria
Angel Francisco Arvelo L.
Existen doce aspirantes para ocupar esos cargos, ocho hombres y cuatro mujeres.
Calcule el número de maneras distintas como se puede formar la directiva, en cada
uno de los siguientes casos:
a) Sin restricciones de ningún tipo.
b) El presidente debe ser hombre y deben estar dos mujeres en la directiva.
c) Deben existir por lo menos dos representantes de ambos sexos en la directiva.
d) Los dos vocales deben ser de diferente sexo.
Solución: a) Sin restricciones es una permutación con repetición, pues podemos
imaginar a los doce aspirantes en fila, el primero es el presidente, y así
sucesivamente, hasta los siete últimos que son los que quedan fuera.
12!
Total de maneras = = 47520
1! 1! 1! 2! 7 !
b) En este caso, se aplica el razonamiento de seleccionar primero y ordenar después.
Se deben seleccionar tres hombres y dos mujeres. El total de maneras de hacer esta
selección es:
FG IJ FG IJ
8 4
56 6 336 .
H KH K
3 2
Una vez seleccionadas las personas se asignan los cargos, el presidente puede ser
de tres maneras, y los cuatro otros cargos se permutan, teniendo en cuenta que el
4!
de vocal está repetido: 3 36
1!1! 2!
Total de maneras = 336 x 36 =12096
c) Hay dos casos: Tres hombres y dos mujeres, o dos hombres y tres mujeres, y una
vez seleccionadas las cinco personas, estas pueden permutarse en los cargos.
Total de maneras =
LMFG IJ FG IJ FG IJ FG IJ OP
8 4
8 4 5!
26880
NH K H K H K H K Q
3 2 2 3 1! 1! 1! 2!
d) La selección de los dos vocales puede hacerse de 8 x 4 = 32, y los otros tres cargos
que son diferentes, pueden ocuparse con las diez personas restantes.
Total de maneras = 32 x V10,3 = 32 x 10 x 9 x 8 = 23040
Ejemplo 22: Se tienen cinco colores distintos para pintar una bandera de tres franjas.
Si no se pueden pintar las tres franjas del mismo color, ¿cuántas banderas diferentes
es posible construir?
Solución: Como hay distinción de orden, se trata de una variación, y hay dos casos
excluyentes: las tres de diferente color, y un mismo color se repite dos veces.
Con tres colores distintos: V5,3 = 5 x 4 x 3 = 60
Con un mismo color dos veces: El color repetido de 5 maneras, el acompañante de
4, y en tres posiciones: 5 x 4 x 3 = 60
Total de banderas = 60 + 60 = 120
Otro razonamiento válido, es restar del total de variaciones de cinco en tres con
repetición, los casos en que se repiten los tres colores.
Total de banderas = 53 – 5 = 120
Ejemplo 22: Se tiene un billete de cada denominación $1, $5, $10, $20, $50 y $100.
¿De cuantas maneras diferentes es posible pagar cuentas exactas con ellos?
12
Teoría Combinatoria
Angel Francisco Arvelo L.
Solución: Es posible pagar todas aquellas cuentas en donde sea necesario
seleccionar uno de ellos, o dos, etc., o hasta los seis.
6 FG IJ FG IJ FG IJ FG IJ FG IJ FG IJ
6
6
6
6
6
26 1 63
1 HK HK HK HK HK HK
2 3 4 5 6
Ejemplo 23: Un profesor solicita a sus diez alumnos que se dividan en cinco grupos
de dos alumnos cada uno, para que cada grupo realice un trabajo sobre un tema igual
para todos los grupos. ¿De cuantas maneras diferentes pueden dividirse?
Ejemplo 25: Al seleccionar dos piedras de las 28 que tiene el dominó, ¿de cuantas
maneras diferentes se puede formar una cadena, es decir, que tengan un número en
común?
Solución: Existen siete piedras con el mismo número, siete blancos, siete unos, etc.,
y se forma una cadena cuando se selecciona un par de ellas.
Ejemplo 27: Se tienen “m” puntos en un plano, de los cuales no hay tres que estén
alineados, con excepción de “n” (3 n < m) que están en una misma línea recta.
Calcule:
a) El número de líneas rectas que se pueden trazar al unir dos de esos puntos.
b) El número de triángulos que se pueden formar al unir tres de ellos.
Solución: a) Si no existieran puntos alineados, el número total de rectas que se
Paso 4: Pasamos a buscar las particiones del grupo G2, formado por
todas aquellas en dos bloques donde no interviene d.
Estas son S (3,2)=3 : {{a} ,{b, c }} ; {{b},{a, c}}; {{c} , {a, b}}
Paso 5: A cada una de ellas que tienen dos bloques, le añadimos {d}
como tercer bloque, y resultan
{{a} ,{b, c },{d}} ; {{b},{a, c},{d}}; {{c} , {a, b},{d}}
Total de particiones de G2 = 3
S(4,3) = 3 S(3,3) + S(3,2) = 3+3 = 6 particiones de G1 ∪ G2
Primera={a,d}, {b},{c}}, Segunda={{a},{b,d},{c}} ,Tercera= {{a}, {b},{c,d}}
Cuarta={{a},{b, c},{d}}; Cuarta={{b},{a, c},{d}}; Sexta= {{c} , {a, b},{d}}
n/k 1 2 3 4 5 6 7 8 9 10 Bell
1 1 1
2 1 1 2
3 1 3 1 5
4 1 7 6 1 15
5 1 15 25 10 1 52
6 1 31 90 65 15 1 203
7 1 63 301 350 140 21 1 877
8 1 127 966 1701 1050 266 28 1 4140
9 1 255 3025 7770 6951 2646 462 36 1 21147
10 1 511 9330 34105 42525 22827 5880 750 45 1 115975
19
Teoría Combinatoria
Angel Francisco Arvelo L.
Solución: a) En el primer caso, las cajas están numeradas con los dígitos
1, 2, 3 y 4 , y podríamos imaginar una fila de 8 casillas, en donde a cada
puesto de la casilla le corresponde a un color.
Así por ejemplo, la primera casilla al color verde, la segunda al color rojo,
la tercera al blanco, y asì sucesivamente.
Con este artificio, cada fila señala en cual caja está colocada la pelota de
ese color, y por ejemplo la fila 44122313, indica que la pelota de color
verde esta colocada en la caja 4, la de color rojo también en la 4, la blanca
en la 1, etc
Este arreglo es una variación con repetición de 4 números en 8 puestos,
y por lo tanto, el total de maneras V`4,8= 48 = 65536 formas
b)En este segundo caso, las cajas no son distinguibles, y puede ser visto
como las diferentes particiones del conjunto {a, b, c d, e, f, g, h}, con 8
elementos distinguibles , donde cada letra representa a un color.
Por ejemplo, la partición B1= {a, b, c}, B2= {d, e} , B3= {f, g, h} representa
la colocación de los colores {a, b, c} en una caja, los colores {d, e} en
otra, y los {f, g, h} en una tercera
20
Teoría Combinatoria
Angel Francisco Arvelo L.
Hacer la partición en una parte, significaría colocar las 8 pelotas en una
misma caja, y dejar las otras tres vacías
Sin embargo, estas particiones podrían realizarse de varias maneras, en
una parte, en dos, en tres o en cuatro.
Las formas de hacer cada una de estas particiones se puede calcular por
los procedimientos explicados en esta sección, o más fácilmente
haciendo uso de la tabla con n= 8 y k=1, 2, 3, 4, obteniendo:
S( 8,1) = 1 ; S(8,2)= 127 ; S(8,3) =966 ; S(8,4)= 1701
Total de maneras = 1+ 127+ 966 + 1701 = B(4) = 2795
Para contar las que caen en el grupo G2, hay que observar que
estas coinciden de manera biunívoca con p4(4)
En efecto, la partición de 4 en 4 partes es única 4= 1+1+1+1
Como también es única la partición en G2, es 8= 2+2+2+2
RESTRICCIONES GENERALES
1. Todos los objetos deben quedar colocados dentro de alguna caja;
es decir, no se permite que queden objetos sobrantes
2. Dentro de las cajas no existen casillas o compartimientos, que
permitan establecer un orden para los objetos en ella colocados
RESTRICCIONES PARTICULARES
Ninguna adicional a las A lo sumo un objeto Ninguna caja puede
generales dentro de una caja quedar vacía
Se colocan a todos los Dentro de cada caja Cada caja debe contener
objetos, de una manera sólo se puede colocar a por lo menos a un objeto.
completamente arbitraria lo sumo, a un objeto.
dentro de cualquiera de No se permite que queden
las cajas. cajas vacías
En una misma caja se Pueden quedar cajas
pueden colocar tantos vacías
objetos como se quiera.
Pueden quedar cajas
vacías
En lo sucesivo:
n = Número de objetos
k= Numero de cajas
Este caso se identifica como una partición del número natural “n” en a lo
sumo “k” partes.
En efecto, supongamos que tenemos un conjunto de cinco objetos
indistinguibles para colocar en tres cajas indistinguibles.
Como no existen restricciones en la colocación, y tanto objetos como
cajas son indistinguibles, se tienen las siguientes opciones:
Colocar a los cinco objetos en una misma caja, y dejar a los otras
dos vacías.
Esta opción equivale a realizar la partición de “n” en una sola parte:
p1(5) =1
Repartir a los cinco objetos en dos cajas, dejando a la otra caja
vacía
Esta opción equivale a realizar la partición de “n” en dos partes
p2 (5) = 2 ( Ver tabla de particiones de un número natural)
Repartir a los cinco objetos entre las tres cajas, sin dejar cajas
vacías
Esta opción equivale a realizar la partición en tres partes
p3 (5)= 2 ( Ver tabla de particiones de un número natural)
1 𝑖=𝑘
𝑘
𝑆(𝑛, 𝑘 ) = ∑ (−1)𝑘−𝑖 ( ) 𝑖 𝑛
𝑘! 𝑖=0 𝑖
Ejemplo 33: Diez monedas van a ser repartidas entre tres personas.
¿De cuantas maneras diferentes puede hacerse el reparto, si cada
persona debe recibir al menos dos monedas?
a) Considere que las diez monedas son del mismo valor
b) Considere que las diez monedas son de diferente valor
32
Teoría Combinatoria
Angel Francisco Arvelo L.
Solución: Las distintas maneras de hacer el reparto puede ser visto como
la colocación de 10 monedas en tres cajas distinguibles A, B y C, que
representan a las personas
a) En este caso, las monedas son indistinguibles, de manera que el
reparto puede hacerse en dos etapas.
En la primera etapa se colocan dos monedas en cada caja, con lo
cual queda satisfecho el requisito de que cada persona debe recibir
por lo menos dos monedas
En la segunda etapa se reparten sin restricción alguna, las cuatro
monedas restantes en las tres cajas, dando como resultado:
, 3+4−1 6
𝐶3,4 =( ) = ( ) = 15 𝑚𝑎𝑛𝑒𝑟𝑎𝑠
4 4
b) Las particiones del número natural 10 en 3 partes son, según la
tabla p3(10)= 8 ; pero dada la restricción de que cada persona debe
recibir por lo menos dos monedas, sólo deben ser consideradas
como válidas, aquellas particiones del grupo G2, es decir aquellas
en donde no interviene el 1
Sabemos que las particiones que caen en el grupo G2 coinciden
con pk(n-k) , en este caso con p3(7)= 4
Esas 4 particiones de 10 en tres partes, donde no interviene el 1
son: 10= 6+2+2 = 5+3+2 = 4+ 4 + 2 = 4+3+3
Para calcular las formas de reparto, podemos imaginar a las 10
monedas colocadas en un orden lineal, donde las primeras
monedas le corresponden a la persona A, las siguientes a B y las
últimas a C.
Las formas de reparto para cada partición son las permutaciones
de las 10 monedas, con repetición tantas veces como monedas le
correspondan.
Finalmente es necesario también permutar a las personas, porque
no necesariamente A debe ser el primero en recibir sus monedas,
B el segundo y C el tercero.
10! 3!
Para la partición 6+2+2: ∙ = 3780 maneras
6!2!2! 1!2!
10! 3!
Para la partición 5+3+2: ∙ = 15120 maneras
5!3!2! 1!1!1!
10! 3!
Para la partición 4+4+2: ∙ = 9450 maneras
4!4!2! 1!2!
10! 3!
Para la partición 4+3+3: ∙ = 12600 maneras
4!3!3! 1!2!
Solución: Los tres ceros pueden ser vistos como objetos no distinguibles
entre sí, al igual que los diez unos.
Imaginemos ocho cajas distinguibles, llamadas A,B,C,D,E,F,G colocadas
en fila en ese orden, una al lado de la otra.
Formar un número binario que tenga las características exigidas,
equivale a colocar un cero en cada una de las cajas B ,D y F, colocando
además un uno en la caja C y otro en la E para garantizar que los ceros
no queden consecutivos
Esta primera operación sólo puede ser ejecutada de una única forma, y
una vez cumplida, restan ocho unos, que pueden ser repartidos de
manera arbitraria entre las cajas A, C, E y G
37
Teoría Combinatoria
Angel Francisco Arvelo L.
En conclusión, la respuesta a la pregunta es:
4+8−1 11
( )=( ) = 165 números binarios
8 8
Preguntas de Revisión
1°) Explique y cite ejemplos del caso, donde una combinación sin repetición coincide
con una permutación con repetición.
7°) Considere un universo donde existen “m” elementos, donde algunos de ellos son
indistinguibles entre sí
Si se selecciona un muestra sin reemplazo de “n” elementos (n < m), ¿es válido
𝑚
aplicar la fórmula 𝐶𝑚,𝑛 = ( ) , para calcular el total de maneras distinguibles de
𝑛
seleccionar dicha muestra? , y en caso de no serlo, explique el procedimiento a seguir
para calcularlas.
Aplique lo anterior en el siguiente ejemplo:
Se selecciona sin reemplazo, una muestra de tres fichas provenientes de una caja
que contiene cuatro blancas no distinguibles, una negra, una roja, una azul, y una
verde.
a) ¿Cuántos resultados distinguibles puede arrojar la muestra?
b) Si las cuatro blancas estuviesen numeradas y por lo tanto fuesen distinguibles,
¿cuántos resultados distinguibles puede arrojar la muestra?
Solución: a) 15 b) 56
2°) Investigue acerca de las permutaciones cíclicas o circulares, su diferencia con las
permutaciones lineales, y su fórmula de cálculo.
Aplique lo investigado para resolver el siguiente ejercicio:
¿De cuantas maneras se pueden sentar siete personas alrededor de una mesa
circular?
a) Sin restricciones
b) Si dos de ellas no deben quedar juntas
Solución: a) 720 b) 480
3°) Investigue acerca de los números de Stirling? ¿Cuáles son los del primer tipo, y
cuales los del segundo? ¿Cuáles son sus propiedades?
Problemas Propuestos
I. Nivel Elemental
1º) Para formar las placas de un automóvil, hay que seleccionar dos letras cualquiera
de las 24 del alfabeto, y tres dígitos del 0 al 9. ¿Cuántas placas diferentes existen, si
se permite la repetición tanto de letras como de dígitos?
Solución : 576.000
2º) ¿De cuantas maneras pueden repartirse sin repetición, tres premios entre cinco
aspirantes, si los premios son: a) iguales. b) diferentes. ?
Solución: a) 10 formas. b) 60 formas.
39
Teoría Combinatoria
Angel Francisco Arvelo L.
3 º) Con tres vocales y tres consonantes diferentes entre sí. ¿Cuantas palabras
distintas de seis letras pueden formarse, con la condición de que no haya dos
vocales, ni dos consonantes juntas? Solución: 72 palabras.
5 º) ¿De cuantas maneras diferentes se pueden repartir las 28 piedras del dominó,
entre los cuatro jugadores ?. Solución: 4,725183 x 1014
6 º) Con tres vocales y tres consonantes diferentes entre si. ¿Cuantas palabras
distintas de seis letras pueden formarse, con la condición de que no haya dos
vocales, ni dos consonantes juntas? Solución: 72 palabras.
11 º) El menú de un restaurante permite con un precio único, elegir una sopa, una
carne con dos acompañantes, una bebida, un postre y café o té.
Existen tres tipos de sopa, tres variedades de carne, cinco acompañantes, cuatro
bebidas y cinco postres.
¿De cuantas formas puede un cliente que haga la selección completa, ordenar su
comida? Solución: 3.600
14 º) Una junta directiva de cinco cargos diferentes, debe estar formada por 3
hombres y 2 mujeres. ¿De cuantas maneras diferentes se puede formar dicha junta,
si se dispone de 7 hombres y de 5 mujeres? Solución: 42.000
40
Teoría Combinatoria
Angel Francisco Arvelo L.
19 º) Siete personas, entre las cuales sólo dos conducen, alquilan dos vehículos
distintos, que tienen una capacidad de cinco puestos cada uno. ¿De cuantas formas
pueden distribuirse entre los dos vehículos? Solución: 60
20 º) Una señora posee tres anillos diferentes, que puede ponérselos en ocho
dedos de la mano. ¿De cuantas formas puede lucirlos si:
a) no puede llevar más de un anillo por dedo?.
b) puede llevar uno o más anillos por dedo?
c) puede llevar uno o más anillos por dedo, y además importa el orden de los anillos
en el dedo? Soluciones: a) 336 b) 512 c) 720
21 º) Se trazan diez rectas en un mismo plano, cuatro paralelas entre sí, y otras seis
no paralelas a la anteriores, ni entre sí. ¿Cuál es el máximo número de puntos de
corte, que es posible encontrar? Solución: 39
24 º) ¿De cuantas maneras pueden distribuirse seis juguetes diferentes entre cuatro
niños, de modo que a cada niño le corresponda un juguete por lo menos?
Solución: 1560 maneras.
26 º) En una caja hay ocho pelotas, de las cuales tres son blancas y no
distinguibles, y cinco son de otros colores todos diferentes. ¿De cuantas maneras
distinguibles se pueden sacar tres pelotas? Solución: 26
28º) ¿Cuántos ceros tiene el factorial del número 150? Solución: 37 ceros
29º) Utilice las propiedades de los números de Stirling del segundo tipo, para
calcular: a) S (12,6) b) S (12,9) c) S (13,5)
Solución a) 1.323.652 b) 22.275 c) 7.508.501
30º) ¿En cuántos números de tres cifras, es decir, comprendidos entre 100 y 999,
el dígito central es el promedio de los dos dígitos extremos? Solución 45
31º) Un pelotón de 15 soldados debe ser dividido en 3 grupos de cinco cada uno
Si cada grupo debe tener un soldado jefe ¿De cuantas maneras se puede hacer
esta división?
a) Si cada grupo va a ser enviado a una región diferente
b) Cada grupo va a realizar simultáneamente la misma tarea
Solución: a) 94.594.500 b) 15.765.750
35º) Un banco impone a sus clientes las siguientes reglas, para seleccionar la
clave de cajero automático:
Debe tener cuatro dígitos distintos
No puede comenzar por cero
No puede tener cuatro dígitos consecutivos en forma ascendente ni
descendente
¿Cuántas claves diferentes existen?
Solución: 4523
Nivel Avanzado
37º) El examen de admisión a una Universidad consta de tres pruebas, cada una de
las cuales es evaluada en una escala de 0 a 200 puntos.
Una prueba con nota inferior a 50 puntos, no es tomada en cuenta para la
totalización final del examen.
Para ser admitido, la totalización de las notas obtenidas debe ser de 200 puntos
como mínimo.
¿De cuantas maneras puede un aspirante obtener esta calificación mínima?
Solución: 1632
39 º) La primera fila de un teatro tiene “n” butacas. ¿De cuantas maneras pueden
sentarse tres personas, con la condición de que por lo menos dos de ellas queden
juntas? Solución: 6 (n - 2)2
40 º) Se tienen “n” puntos en el plano tales que tres cualesquiera de ellos no son
colineales, y se trazan todas las rectas posibles al unir cada par de puntos.
Hallar el número máximo de puntos de intersección entre las rectas trazadas.
n(n3 6n2 11n 2)
Solución:
8
41 º) Halle la suma de todos los números de cinco cifras (repetidas o no), que se
pueden formar con los dígitos 1, 2, 3 y 4. Solución: 28.444.160
43º) Los números binarios utilizan como dígitos sólo al cero y al uno. Suponga que
se quiere formar un número binario que contenga “n” ceros y “k” unos (n > k) , con
la condición de que los unos no estén nunca en forma consecutiva. ¿Cuántos
números binarios diferentes es posible formar? Solución:
n 1 n 1 n 1 n 1
2
n k n k 1 n k 1 n k 1
44
Teoría Combinatoria
Angel Francisco Arvelo L.