Download Análisis Combinatorio

ANGEL FRANCISCO ARVELO LUJAN
Angel Francisco Arvelo Luján es un Profesor Universitario Venezolano en el área
de Probabilidad y Estadística, con más de 40 años de experiencia en las más
reconocidas universidades del área metropolitana de Caracas.
Universidad Católica “Andrés Bello”: Profesor Titular Jubilado 1970 a 2003
Universidad Central de Venezuela: Profesor por Concurso de Oposición desde
1993 al presente
Universidad Simón Bolívar: Profesor desde 2005 al presente
Universidad Metropolitana: Profesor desde 1973 a 1987
Universidad Nacional Abierta: Revisor de contenidos, desde 1979 hasta 2004
Sus datos personales son :
Lugar y Fecha de Nacimiento: Caracas, 16-02-1947
Correo electrónico: [email protected]
Teléfono: 58 416 6357636
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 al
Presente
El Profesor Arvelo fue Director de la Escuela de Ingeniería Industrial de la
Universidad Católica “Andrés Bello” (1974-1979) , Coordinador de los Laboratorios
de esa misma Universidad especializados en ensayos de Calidad, Auditor de
Calidad, y autor del libro “Capacidad de Procesos Industriales” UCAB 1998.
En numerosas oportunidades, el Profesor Arvelo ha dictado cursos empresariales
en el área de “Estadística General” y “Control Estadístico de Procesos”.
Otras publicaciones del Prof. Arvelo pueden ser bajadas de su página web:
www.arvelo.com.ve , en la sección PDFS.
1
Análisis Combinatorio
Angel Francisco Arvelo L.
ANÁLISIS COMBINATORIO
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 este 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 numero 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, 4cuatro 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 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.
11.1 Combinaciones: Estos son arreglos en donde el orden de colocación de
los elementos que lo integran no se contabiliza como diferente de otro que tenga a
los mismos elementos en otro orden; de manera que todos aquellos arreglos que
tengan a los mismos elementos, se contabilizan como uno sólo, aunque estos
elementos estén colocados en diferente orden.
En una combinación, para que un arreglo sea diferente de otro, es necesario que
por lo menos un elemento sea diferente, o que un mismo elemento aparezca un
número diferente de veces.
a) Combinaciones sin repetición: Este es el caso en que el universo tiene “m”
elementos todos diferentes entre si, y se seleccionan “n” de ellos, sin que se
permita que un mismo elemento intervenga más de una vez.
Ejemplo 11.1 : Supongamos que el universo esta formado por cinco elementos
{a,b,c,d,e} , y que de ellos se seleccionan tres sin repetición.
Las diferentes combinaciones que se pueden formar con ellos son:
abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde
Nótese que la combinación cba , no ha sido incluida en la lista, por considerarla
idéntica a las abc, al tener los mismos elementos.
2
Análisis Combinatorio
Angel Francisco Arvelo L.
Existen fórmulas combinatorias, que se deducen fundamentalmente por inducción,
y cuya deducción puede encontrarse en textos de Álgebra, y que permiten calcular
el número de combinaciones que se pueden formar, sin tener que hacer la lista.
Para el caso de las combinaciones sin repetición, esta fórmula establece que:
m
m!
Cm,n
n
n! (m n)!
La expresión C m,n se lee como combinaciones de “m” en “n” ; mientras que “!” se
FG IJ
H K
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,
5
5!
5 4 3 2 1
tendríamos: C5,3
= 10 combinaciones.
3
3! (5 3)! 3 2 1 2 1
FG IJ
HK
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:
m
m
1°)
; esta propiedad se conoce como “propiedad de complemento”,
n
m n
y resulta obvia, pues por cada combinación de los elementos que intervienen en el
arreglo, existe otra entre los elementos que no intervienen.
FG IJ FG
H K H
2°)
IJ
K
FGmIJ FGm 1IJ FGm 1IJ ;
Hn K Hn 1 K H n K
esta propiedad se conoce como “Propiedad de
Steefel”, y establece que el total de combinaciones se descompone en dos;
m 1
combinaciones donde interviene un elemento particular
, y combinaciones
n 1
donde no interviene ese elemento particular
En el ejemplo 11.1 se tiene :
FG 4IJ
H 2K
FG 5IJ FG 4IJ FG 4IJ
H 3K H 2K H 3K
FGm 1IJ .
H nK
FG
H
IJ
K
representa las combinaciones donde interviene un elemento, digamos “a”
pues él ocupa un lugar y por tanto restan 4 para seleccionar 2 que lo acompañen ,
4
mientras que
representa las combinaciones donde no interviene “a”, él queda
3
excluido y quedan 4 para seleccionar 3.
FG IJ
HK
3
Análisis Combinatorio
Angel Francisco Arvelo L.
3°)
FGm m IJ FGm IJ FGm IJ FGm IJ FG m IJ FGm IJ FG m IJ
H n K H 0 K H n K H 1 K H n 1K H 2 K H n 2K
1
2
1
2
1
2
1
2

FGm IJ FGm IJ ; RSm
H n K H 0 K Tm
1
2
1
n
n
Esta propiedad se conoce como “Propiedad de Vandermonde” y se interpreta de la
siguiente manera:
Supongamos que un grupo hay 8 personas, 5 Hombres y 3 mujeres, y de ellos se
van a seleccionar 3 para formar una comisión.
8
5 3
5 3
5 3
5 3
3
0 3
1 2
2 1
3 0
El total de comisiones que se pueden formar queda descompuesto en varios
casos, aquellos en donde intervienen ningún hombre y tres mujeres, o un hombre
y dos mujeres, o dos hombres y una mujer, o tres hombres y ninguna mujer.
n
n
n
n
4°)

= 2n ; según esta propiedad, la suma de todos los
0
1
2
n
números combinatorios con el mismo numerador da por resultado 2 n
n
n
n
n
n
n
5°)

 = 2n-1
0
2
4
1
3
5
2
FG IJ FG IJ FG IJ FG IJ FG IJ FG IJ FG IJ FG IJ FG IJ
H K H KH K H KH K H KH K H KH K
FG IJ
HK
FG IJ
HK
FG IJ
HK
FG IJ
HK
FG IJ
HK
FG IJ
HK
FG IJ
HK
FG IJ FG IJ FG IJ
HK HK HK
b) Combinaciones con repetición: Este es el caso en que se permite que un
mismo elemento del universo intervenga mas de una vez en el arreglo.
Ejemplo 2 : Si a los elementos del Ejemplo 1 se les permite intervenir mas 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.
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
m n 1
lista, y según la cual: Cm' ,n
; donde Cm' ,n representa el número de
n
combinaciones con repetición de “m” elementos seleccionando “n”.
5 3 1
7
En el caso anterior: C'5,3
= 35
3
3
Ejemplo 3 : Calcular el número de piedras que tiene el dominó ordinario.
Solución: La formación de las piedras del dominó es un caso típico de una
combinación con repetición, pues de un universo de 7 números {0,1,2,3,4,5,6} , se
seleccionan dos para formar una piedra.
Es una combinación, pues no hay distinción entre la piedra 1-4 por ejemplo con la
4-1, y es con repetición para formar los dobles.
En consecuencia, el número de piedras diferentes es:
7 2 1
8
= 28
C7' ,2
2
2
FG
H
IJ
K
IJ FG IJ
K HK
FG
H
FG
H
IJ FG IJ
K HK
4
Análisis Combinatorio
Angel Francisco Arvelo L.
En el caso del dominó cubano, que va desde el 0 hasta el 9, el número de piedras
10 2 1
11
'
es:
= 55
C10
,2
2
2
FG
H
IJ FG IJ
K H K
2 Variaciones: Se llaman variaciones a aquellos arreglos en donde el orden de
colocación es un criterio para diferenciar a un arreglo de otro, aunque los
elementos que lo integren sean los mismos.
En una variación un arreglo es distinto de otro cuando por lo menos un elemento
es distinto, o cuando siendo los mismos elementos, están colocados en diferente
orden.
a) Variaciones sin repetición: No se permite que ningún elemento del universo,
se repita en el arreglo.
Ejemplo 4 : Con los elementos del universo {a,b,c,d}, definir todas las variaciones
de a dos, que puedan formarse, sin repetir elementos.
Solución: Por ser una variación, el orden de colocación diferencia a un arreglo de
otro, por lo tanto, las variaciones de a dos sin repetición, son las siguientes doce:
ab, ac, ad, ba, bc, bd , ca cb , cd , da , db , dc
La fórmula combinatoria que permite calcular el numero de variaciones sin
repetición, que pueden formarse con universo de “m” elementos, seleccionando
m!
m(m 1)(m n 1)
“n” de ellos, es: Vm,n
(m n)!
4!
4 3 = 12
Aplicando está fórmula en el Ejemplo 4 se tiene: V4,2 =
(4 2)!
b) Variaciones con repetición: Se permite que los elementos del universo, que
son todos diferentes entre sí, se repitan en el arreglo.
Ejemplo 5 : Con los elementos del ejemplo 4, definir todas las variaciones de a
dos, que puedan formarse.
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.
La fórmula combinatoria para calcular las variaciones con repetición establece:
Vm' ,n mn
En el ejemplo 5: V4' ,2
42 =16
3 Permutaciones: Se llaman permutaciones a aquellos arreglos en donde se
seleccionan con distinción de orden, a todos los elementos del universo.
a) Permutaciones sin repetición: En este caso, todos los elementos del universo
son distintos entre si.
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
5
Análisis Combinatorio
Angel Francisco Arvelo L.
El cálculo de las permutaciones de “n” elementos sin repetición, es un caso
particular de las variaciones sin repetición donde m = n , y por lo tanto:
n!
Pn Vn,n
Pn = n!
(n n)!
En el ejemplo 6, se tiene : P4 = 4! = 24 .
b) Permutaciones con repetición: En el universo existen elementos repetidos, y
se seleccionan todos con distinción de orden.
Ejemplo 7 : Con los elementos del universo {a,a,b,c}, definir todas las
permutaciones posibles.
Solución: Se seleccionan todos, y se ordenan. Las permutaciones posibles son:
aabc , aacb , abac , acab , abca , acba , baac , caab , baca , caba , bcaa , cbaa
El número de permutaciones con repetición se calculan mediante la expresión:
n
n!
Pn;n1,n2 nk
n1,n2 ,nk
n1 ! n2 !nk !
FG
H
IJ
K
donde:.n1 = número de elementos repetidos del tipo 1
n2 = número de elementos repetidos del tipo 2
nk = número de elementos repetidos del tipo k
n= número de elementos en el universo = n 1 + n2 +....+ nk
En el universo del ejemplo 7 , existen 3 tipos de elementos , a , b y c ; pero la “a”
está dos veces y los otros una vez.
Por tanto n1 = 2 , n2 = 1 , n3 = 1 , n = 2+1+1 = 4 , y el número de permutaciones
4
4!
es: P4;2,11,
= 12
211
,,
2!1!1!
Con relación a las permutaciones con repetición se pueden hacer los siguientes
comentarios:
1°) Obsérvese que cuando n1 =1 , n2 = 1 , ...., nk = 1, entonces no hay elementos
repetidos , y el número de permutaciones es n!.
Estos significa que la fórmula de las permutaciones sin repetición, es un caso
particular de la fórmula con repetición , en donde n 1 =1 , n2 = 1 , ...., nk = 1.
2°) Cuando k=2 , es decir cuando en el universo sólo hay dos tipos de elementos,
entonces se tiene : n1 + n2 = n , y en consecuencia:
n
n
n
n!
n!
Pn;n1,n2
Cn,n1 Cn,n2
n1,n2
n1
n2
n1 ! n2 ! n1 !(n n1)!
FG IJ
H K
FG
H
IJ
K
FG IJ FG IJ
H K H K
En este caso, la permutación queda definida al seleccionar los n 1 puestos que le
corresponden a los elementos del tipo 1, pues 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.
6
Análisis Combinatorio
Angel Francisco Arvelo L.
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 .
5
5
5
5!
P5;3,2
10
3,2
3! 2!
3
2
FG IJ
H K
FG IJ FG IJ
HK HK
4 Principios multiplicativo y aditivo:
En muchas oportunidades, los
diferentes tipos de arreglos que hemos considerado no se presentan
aisladamente.
En estas situaciones, se hace necesario clasificar los arreglos en diversos casos,
calcularlos por separado, y al final se presenta a pregunta ¿cuándo se suman?, y
¿cuándo se multiplican?.
La respuesta a esta pregunta la dan los principios multiplicativo y aditivo.
Principio multiplicativo: Si para armar un arreglo es necesario realizar una
secuencia de “k” operaciones, y la primera operación puede realizarse de n 1
maneras, la segunda de n2 maneras, la k-ésima de nk maneras, entonces el
arreglo puede armarse de n1.n2....nk maneras .
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, esta vestido de diferente manera.
El total de formas como puede vestirse es en consecuencia: 2 x 3 x 5 = 30
Principio aditivo: Si existen “k” procedimientos excluyentes para armar un
arreglo, y el primer procedimiento puede realizarse de n 1 maneras, el segundo de
n2 maneras, el k-ésimo de nk maneras, entonces el arreglo puede armarse de
n1+n2+....+nk maneras .
El término excluyente significa que si se realiza por un procedimiento no se puede
realizar por el otro.
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.
EJERCICIOS RESUELTOS
Ejemplo 11: En un salón de clase hay 12 estudiantes, y se va a formar una comisión
de 4 .Calcule el número de comisiones distintas que pueden formarse, en cada uno
de los siguientes casos:
a) No hay jerarquía entre los cuatro miembros de la comisión.
b) Existe jerarquía entre los cuatro miembros de la comisión.
c) Entre los cuatro miembros de la comisión, uno debe ser el presidente, otro el
tesorero, y los otros dos vocales sin jerarquía entre ellos dos.
7
Análisis Combinatorio
Angel Francisco Arvelo L.
Solución: a) Este caso es una combinación pues no existe jerarquía entre los
12
12!
miembros. C12,4
495
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.
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!
12 .
asignarse los cargos es: P4;11, ,2
1! 1! 2!
Aplicando el principio multiplicativo, el total de comisiones diferentes es en
consecuencia : 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!
FG IJ
H K
Ejemplo 12: Un grupo de nueve personas esta formado 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 entre si 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.
Supongamos que las tres personas son A , B y C.
10 !
Con el procedimiento 6+2+2 las formas son : 3 x
= 3780
6 ! 2! 2!
Se trata de una permutación con repetición , pues 6 A , 2 B y 2C pueden estar
colocadas en cualquiera de las 10 posiciones, y multiplicada por 3, porque quien
recibe los seis regalos pude ser cualquiera de los tres .
10 !
Con el procedimiento 5+3+2 las formas son : 3! x
= 15120
5 ! 3 ! 2!
8
Análisis Combinatorio
Angel Francisco Arvelo L.
10 !
= 9450
4 ! 4 ! 2!
10 !
Con el procedimiento 4+3+3 las formas son : 3 x
= 12600
4! 3! 3!
Con el procedimiento 4+4+2 las formas son : 3 x
Aplicando el principio aditivo, 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 en que orden se
emitieron.
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 en doce
posiciones, sin distinción de orden ; en consecuencia el total de escrutinios
3 12 1
14
diferentes es:
C'3,12
91
12
12
FG
H
IJ FG IJ
K H K
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 : a) Existen la alternativa de no tapar ninguno de los agujeros, o tapar uno,
o tapar dos ,etc., hasta tapar los cuatro.
9
Análisis Combinatorio
Angel Francisco Arvelo L.
El total de sonidos diferentes es entonces:
FG 4IJ FG 4IJ FG 4IJ FG 4IJ FG 4IJ
H 0K H1K H 2K H 3K H 4K
24
16
Ejemplo 17 : La dirección de un liceo otorga a los mejores estudiantes, premios en
Ciencias, Literatura e Idiomas.
Cada premio tiene dos niveles: “excelencia” y “mención de honor” , que son
concedidos al primero y segundo estudiante en cada asignatura.
En un salón de clases hay 20 estudiantes. ¿De cuantas formas diferentes pueden
ser concedidos los tres premios?.
Solución : a) En cada asignatura, las formas de conceder los premios representan
una variación sin repetición, pues importa el orden y no puede repetirse el mismo
estudiante en el primero y segundo lugar. V20,2 = 20 x 19 = 380.
Al considerar las tres asignaturas, se trata de una variación con repetición, pues los
premiados en una, pueden repetir en otra, y hay distinción entre las asignaturas.
Total de formas = (380)3 = 54.872.000 formas
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.
15
Total de formas = V6,2
6 5 5005 =150150
6
FG IJ
H K
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 20 : El director de una empresa debe formar un equipo de trabajo.
El equipo puede estar formado por tres o por cuatro personas, y debe elegir entre
seis de sus empleados, pero teniendo en cuenta que dos de ellos no pueden
trabajar juntos. ¿ De cuantas maneras distintas puede formar el equipo?.
Solución : Hay dos casos excluyentes, que son:
6
4
1°) Decide formar el equipo con tres personas:
= 16 formas
3
1
FG IJ FG IJ
HK HK
F 6I F 4I
2°) Decide formar el equipo con cuatro personas: G J G J = 9 formas
H 4K H 2K
Total de formas = 16 + 9 = 25
10
Análisis Combinatorio
Angel Francisco Arvelo L.
Ejemplo 21: La junta directiva de una empresa tiene cinco cargos, presidente,
secretario, tesorero y dos vocales.
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) Si 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
8 4
esta selección es:
56 6 336 .
3 2
Una vez seleccionadas las personas se asignan los cargos, el presidente puede ser
de tres maneras, y los otros cargos se permutan, teniendo en cuenta que el de
4!
36
vocal está repetido: 3
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
seleccionadas las cinco personas, estas pueden permutarse en los cargos.
8 4
8 4
5!
Total de maneras =
26880
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
FG IJ FG IJ
H KH K
LMFG IJ FG IJ FG IJ FG IJ OP
NH K H K H K H K Q
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
3!
Con un mismo color dos veces: V5,2
= 5 x 4 x 3 = 60
2! 1!
Total de banderas = 60 + 60 = 120
Otra manera de resolverlo, es restar del total de variaciones de cinco en tres con
repetición, los casos en que se repiten los tres colores.
11
Análisis Combinatorio
Angel Francisco Arvelo L.
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? .
Solución: Es posible pagar todas aquellas cuentas en donde sea necesario
seleccionar uno de ellos, o dos, etc., o hasta los seis.
6
6
6
6
6
6
26 1 63
1
2
3
4
5
6
FG IJ FG IJ FG IJ FG IJ FG IJ FG IJ
HK HK HK HK HK HK
Ejemplo 23: Un profesor le pide 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?
Solución : Si cada grupo fuese a desarrollar un tema diferente, el total de maneras
de hacer la división sería una permutación con repetición, pues pudiésemos
imaginar a los diez alumnos en fila, y a los dos primeros les toca el primer tema, al
tercero y cuarto de la fila el segundo tema y así sucesivamente.
10!
113400
Con temas diferentes, las maneras de hacer la división sería:
2! 2! 2! 2! 2!
Sin embargo, como el tema es el mismo, aquí hay divisiones idénticas.
Por ejemplo, imaginemos que la fila de alumnos es A B C D E F G H I J.
En esta fila los cinco grupos son A con B , C con D , E con F , G con H e I con J.
Estos cinco grupos serían los mismos que en la fila D C I J B A E F G H .
En consecuencia, existen 5! = 120 formas de hacer la división con temas diferentes
que equivalen a una sola con el mismo tema, y por lo tanto:
113400
945
Formas de hacer la división =
120
Ejemplo 24: Diez libros diferentes , tres de Matemática , dos de Física y cinco de
Gramática van a ser ordenados en fila, en una biblioteca. ¿De cuantas maneras
pueden ordenarse, de forma que los de una misma materia queden juntos?.
Solución : Cada materia puede ser vista como un bloque de libros, y por lo tanto
pueden ordenarse de 3! Formas, y adicionalmente los libros de cada materia
pueden permutarse dentro del bloque.
Maneras de ordenarlos = 3! x 3! x 2! x 5! = 8640
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.
7
Las formas de seleccionar dos piedras de un mismo número es
= 21 ; y como
2
la cadena puede ser con cualquiera de los siete números, se tiene que el total de
maneras para formar la cadena es: 7 x 21 = 147
FG IJ
HK
12
Análisis Combinatorio
Angel Francisco Arvelo L.
Ejemplo 26 : ¿Cuántos números naturales entre 1 y 100.000, tienen la propiedad de
que la suma de sus dígitos es 7?.
Solución: Cualquier número natural entre 1 y 100.000, a excepción de éste ultimo
que no tiene la propiedad exigida, puede ser escrito con cinco dígitos, y la suma de
sus dígitos será 7 en casos como 00007, 4210 como 04210, etc.
El problema puede ser visto entonces, como repartir siete monedas iguales entre
cinco cajas, donde la primera caja representa la unidad de diez mil, la segunda la
unidad de mil, la tercera la centena, la cuarta la decena y la quinta la unidad.
Así por ejemplo, el número 04210 que tiene la propiedad, puede ser visto como el
caso donde se colocan 4 monedas en la segunda caja, dos en la tercera, una en la
cuarta y ninguna en la primera y en la última.
Esta forma de repartir es una combinación con repetición, pues al ser las monedas
iguales, lo que interesa es cuantas monedas se colocan en cada caja, y no su orden
de colocación; así por ejemplo el reparto 2222334 es idéntico al reparto 3423222,
pues en cada uno, la caja 2 recibe cuatro monedas, la 3 dos y la 4 una.
Bajo este punto de vista, el problema se reduce a combinar cinco elementos en
siete posiciones con repetición, y el total de números con la propiedad es:
5 7 1
11
C'5,7
330
7
7
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 numero 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
m
pudieran trazar sería
.
2
Sin embargo, como hay “n” alineados, todas las combinaciones entre ellos definen a
la misma recta, que debe ser contabilizada una sola vez.
n
El número de combinaciones que definen a la misma recta es:
2
FG
H
IJ FG IJ
K H K
FG IJ
H K
Total de rectas que se pueden trazar =
FGmIJ FGnIJ
H 2 K H 2K
FG IJ
HK
1
La razón de sumar 1 , es porque al restar todas las combinaciones que se definen a
la misma recta, ésta no estaría siendo considerada dentro del conjunto de rectas
que pueden ser trazadas.
b) Con un razonamiento similar al anterior, si no existieran puntos alineados, el total
m
de triángulos que pudiesen ser formados sería :
.
3
Pero las combinaciones entre los puntos alineados, definen una recta y no un
triángulo , y deben ser restadas de las anteriores.
m
n
Total de triángulos que se pueden formar =
3
3
FG IJ
H K
FG IJ FG IJ
H K HK
13
Análisis Combinatorio
Angel Francisco Arvelo L.
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.
2°) Demuestre e interprete, la siguiente expresión:
nk
n n n1 n n1 n2
n!
; donde: n = n1+n2+n3+....+nk

n1
n1 ! n2 ! n3 !nk !
n2
n3
nk
FG IJ FG
H KH
IJ FG
KH
IJ FG IJ
K H K
3°) ¿Por qué es necesario que los procedimientos sean excluyentes para poder
aplicar el principio aditivo?.
Cite ejemplos de situaciones en donde no sean excluyentes.
4°) ¿En qué se convierte una variación sin repetición cuando m = n ?.
5°) Interprete la expresión: Vm,n = Cm,n
x
Pn .
6°) Demuestre e interprete desde el punto de vista combinatorio, la siguiente
expresión: Vm,n = Vm-1,n + n Vm-1,n-1 .
7°) En un universo donde existen “m” elementos , algunos de ellos son
indistinguibles entre si. Se seleccionan del universo “n < m” sin repetición.
Si existe distinción de orden en el arreglo , ¿se puede aplicar la fórmula de las
variaciones sin repetición, para calcular el número total de arreglos diferentes?.
Si no existe distinción de orden en el arreglo , ¿ se puede aplicar la fórmula de las
combinaciones sin repetición en este caso? . Explique y cite ejemplos.
Temas complementarios para investigar
1°) Investigue la deducción matemática de las diferentes fórmulas combinatorias
que aparecen en este capítulo.
2°) Investigue acerca de las permutaciones cíclicas o circulares, su diferencia con
las permutaciones lineales, y su fórmula de cálculo.
3°) Investigue acerca de la “Teoría de Particiones”. ¿ A qué se llaman particiones
distinguibles y no distinguibles? . ¿ Como se calculan ?.
4°) Investigue acerca de la generalización de los números combinatorios. ¿Puede
ser negativo alguno de sus términos?
Problemas Propuestos
I. Nivel Elemental
14
Análisis Combinatorio
Angel Francisco Arvelo L.
28º) 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
29 º) ¿ 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.
30 º) 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.
31 º) ¿ Cuantos juegos diferentes le pueden corresponder a un jugador de dominó,
al seleccionar sus siete piedras ?. Solución: 1.184.040
32 º) ¿De cuantas maneras diferentes se pueden repartir las 28 piedras del dominó,
entre los cuatro jugadores ?. Solución: 4,725183 x 1014
33 º) 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.
34 º) ¿De cuantas formas se pueden colocar tres objetos indistinguibles en ocho
cajas distintas, si cada objeto ocupa una caja ? Solución: 56
35 º) Cuatro personas entre las cuales hay un matrimonio, van a hospedarse en un
hotel, donde existen dos habitaciones matrimoniales y cinco habitaciones sencillas
disponibles. ¿De cuantas maneras distintas pueden alojarse?. Solución: 40
36 º) Cinco personas viajarán en el curso de la semana próxima ( 7 días hábiles).
¿De cuantas formas pueden realizarse esos viajes?.
Solución: 16.807
37 º) Un equipo de fútbol tiene programado nueve partidos contra equipos
diferentes durante la temporada. ¿De cuantas formas puede terminar con cuatro
ganados, dos empatados y tres perdidos?
Solución: 1260
38 º) 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
15
Análisis Combinatorio
Angel Francisco Arvelo L.
39 º) Un automóvil puede llevar dos personas en el asiento delantero y una en el
asiento trasero. Si entre seis personas, solo dos conducen, ¿de cuantas maneras
se puede llenar el automóvil ? . Solución: 40
40 º) En un campeonato de béisbol hay 8 equipos. ¿ Cuantos juegos serán
necesarios, si cada equipo debe jugar dos veces en su campo, contra cada uno de
los contrarios ? .
Solución: 112 juegos
41 º) 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
42 º) Se tienen los números 5874 y 12369. ¿Cuantos números enteros diferentes
pueden formarse, con dos cifras no repetidas del primero y tres no repetidas del
segundo.?
Solución: 7200
43 º) Una persona va a ofrecer una cena para seis invitados.
a) ¿ De cuantas maneras puede seleccionar entre diez de sus amigos?
b) ¿ De cuantas maneras, si entre sus diez amigos hay dos que no pueden estar
juntos?.
Soluciones: a ) 210 b)140
44 º) Un examen de selección múltiple tiene diez preguntas.
Al llenar la hoja de respuestas, el estudiante debe elegir una de tres alternativas,
no responder la pregunta, responder verdadero o responder falso.
¿De cuantas maneras puede llenar la hoja de respuestas?. Solución : 59.049
II. Nivel Intermedio
45 º) ¿Cuántas diagonales tiene un polígono convexo de 12 lados? . Solución: 54
46 º) 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
47 º) Una ciudad está perfectamente cuadriculada como un tablero de ajedrez, es
decir con ocho filas horizontales y ocho columnas verticales.
Una persona se encuentra en la esquina inferior izquierda, y debe caminar hasta la
esquina superior derecha, siguiendo la trayectoria más corta posible.
¿ De cuantas formas puede hacerlo ?. Solución: 12.870
48 º) 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
16
Análisis Combinatorio
Angel Francisco Arvelo L.
49 º) Se trazan diez rectas en un mismo plano, cuatro paralelas entre si, y otras seis
no paralelas a la anteriores, ni entre si. ¿ Cual es el máximo número de puntos de
corte, que es posible encontrar ?.
Solución: 39
50 º) ¿ Cuantas derivadas parciales diferentes de orden cinco, tiene una función de
tres variables independientes ?. Solución: 21
51º) De un conjunto de “m” personas entre quienes se encuentra el Sr. X, se
eligen n < m, para desempeñar “n” cargos diferentes.
a) ¿Cuántas formas de elección son posibles?.
b) ¿Cuántas formas son posibles, sin seleccionar al Sr. X ?.
c) ¿Cuántas formas son posibles, si al Sr. X se le asigna algún cargo?.
d) ¿Qué relación existe entre los tres resultados anteriores ?.
Solución: Véase pregunta de revisión N° 6.
52 º) ¿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.
53 º) En una fiesta hay 8 muchachos y 6 muchachas. ¿De cuantas maneras
distintas pueden estar bailando, si siempre deben estar exactamente cuatro parejas
sobre la pista ? .
Solución: 25.200 maneras
54 º) 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
se pueden sacar tres pelotas ? Solución : 26
55 º) Una familia de cuatro personas debe viajar un determinado día en avión.
Ese día existen seis vuelos con diferentes horarios .
¿ De cuantas maneras pueden organizar el viaje, con dos de ellos en un avión y los
otros dos en otro ?.
Solución : 90
56º) ¿Cuántos ceros tiene el factorial del número 150?. Solución: 37 ceros
Nivel Avanzado
57 º) Demostrar las siguientes identidades combinatorias:
n
n 1
n 2
n r 1
n r
a) 1

1
2
3
r
r
b)
n
0
2
n
1
3
n
2
4
n
n
 ( n 1)
3
n
2
n 1
( n 2)
17
Análisis Combinatorio
Angel Francisco Arvelo L.
c)
m
m 1
n
n 1
n
d)
n
1
2
2
n
1
m 2
n 1

n
3
3
n
2
m n
1
m n 1
0
m 1
n 1
n
 n
n
n
n( n 1)
2
n 1
58 º) 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 .
59 º) 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
60 º) Doce monedas del mismo valor van a ser repartidas entre cuatro personas.
¿De cuantas maneras diferentes se puede hacer el reparto, si cada persona debe
recibir por lo menos una moneda?. Solución: 165
61 º) 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
62 º) Se tienen “n” puntos en el espacio tales que cuatro cualesquiera de ellos no
están sobre un mismo plano, y se construyen todos los planos determinados por
cada terna de puntos. Calcule el número máximo de rectas de intersección que es
n(n 1)(n4 5n3 10n2 80n 60)
posible hallar. Solución:
72
63º) 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