Matemática I

Combinatoria
Alejandro Rı́os

La Combinatoria es la rama de la Matemática que provee principios de

enumeración o conteo que permiten calcular cantidades de determinados ob-
jetos sin realmente tener que contarlos. La Combinatoria tiene aplicación no
sólo en la Aritmética, sino también en otras áreas de la Matemática, tales
como la Teorı́a de la Probabilidad y la Estadı́stica y en Informática, por
ejemplo en la teorı́a de la codificación y en el análisis de algoritmos.
Introduciremos cada uno de los conceptos fundamentales con una serie
de ejemplos y sólo después de ellos daremos la definición del concepto y el
teorema general de conteo correspondiente.

1. Permutaciones
Ejemplo 1.1. ¿De cuántas maneras pueden disponerse las letras A, B, C?
(Sin repetirlas).

Respuesta. Veamos: ABC, ACB, BAC, BCA, CAB, CBA. Luego la

respuesta es 6.
No siempre es fácil contar todas las disposiciones posibles. Tratemos de ra-
zonar: para la primera letra tenemos 3 opciones, y para cada una de estas
opciones, para la segunda letra, podemos elegir cualquiera de las 2 letras
restantes. Para la última letra sólo nos queda una opción. Luego la respuesta
es 3 · 2 · 1 = 3! = 6, y la situación puede representarse ası́:

3
|{z} · |{z}
2 · |{z}
1
1a letra 2a letra 3a letra

Ejemplo 1.2. ¿De cuántas maneras puede finalizar una carrera en la que
intervienen 7 corredores? (No hay empates).

Respuesta. 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040.
El razonamiento es análogo al anterior. Para el primer puesto hay 7 opciones
(cualquiera puede ganar). Para cada una de estas 7 opciones hay 6 opciones
para el segundo puesto (cualquiera, salvo el que salió primero, puede salir
segundo). Y ası́ siguiendo.

1
Ejemplo 1.3. ¿ De cuántas maneras pueden ponerse 10 libros en un estante?
(No hay ejemplares repetidos).
Respuesta. 10! = 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 3.628.800.
Porque el primero puede ser cualquiera de los 10, y para cada una de estas
10 opciones, hay 9 opciones para el segundo, etc..

Ejemplo 1.4. ¿ De cuántas maneras puede conformarse una comisión con

4 candidatos si debe haber un presidente, un vicepresidente, un tesorero y un
secretario?
Respuesta. 4! = 4 · 3 · 2 · 1 = 24.
Porque el presidente puede ser cualquiera de los 4, y para cada una de estas
4 opciones, hay 3 opciones para el vice, y ası́ siguiendo. Gráficamente:
4 · |{z}
|{z} 3 · |{z}
2 · |{z}
1
P V T S

Ahora damos la definición de permutación y a continuación el teorema

que nos dice que el número de permutaciones de n objetos es n!.
Definición 1.1. Una permutación de un conjunto de objetos cualesquiera es
una ordenación o disposición de dichos objetos (ya sea en una lista o fila o
columna, por ejemplo).
Teorema 1.1. La cantidad de permutaciones de n objetos distintos es:
n! = n · (n − 1) · (n − 2) · . . . · 2 · 1 (n factorial)

2. Permutaciones de n tomados de a k
Ejemplo 2.1. ¿De cuántas maneras pueden disponerse tres letras distintas
tomadas del conjunto {A, B, C, D, E}?
Por ejemplo, además de todas las disposiciones del Ejemplo 1.1 tendrı́amos,
entre otras, las siguientes:
ABD, ADB, BAD, BDA, DAB, DBA, ACD, ADC, ADE, ...
Respuesta. Para la primera letra tenemos 5 opciones, y para cada una de
estas opciones, podemos elegir, como segunda letra, cualquiera de las 4 letras
restantes y para cada una de estas 20 = 5 · 4 opciones tenemos tres elecciones
posibles para la tercera letra. Luego la respuesta es 5·4·3 = 60, y la podemos
graficar ası́:
5
|{z} · |{z}
4 · |{z}
3
a a a
1 letra 2 letra 3 letra

Observar que la respuesta puede escribirse ası́:

5·4·3·2·1 5! 5!
60 = 5 · 4 · 3 = = =
2·1 2! (5 − 3)!

2
Ejemplo 2.2. ¿De cuántas maneras puede resultar el podio (los tres prime-
ros) de una carrera en la que intervienen 7 corredores? (No hay empates).
Respuesta. El razonamiento es análogo al anterior. Para el primer puesto
hay 7 opciones (cualquiera puede ganar). Para cada una de estas 7 opciones
hay 6 opciones para el segundo puesto (cualquiera, salvo el que salió primero,
puede salir segundo). Y, finalmente, para el tercer puesto quedan 5 posibili-
dades. Entonces la respuesta es:
7·6·5·4·3·2·1 7! 7!
7·6·5= = = = 210
4·3·2·1 4! (7 − 3)!

Ejemplo 2.3. Tengo 10 libros y quiero ponerlos en un estante donde sólo

caben 6 cualesquiera de ellos.¿De cuántas maneras puedo ubicarlos? (No hay
ejemplares repetidos).
Respuesta. El primero puede ser culquiera de los 10, y para cada una de
estas 10 opciones, hay 9 opciones para el segundo, y ası́ siguiendo. Entonces
la respuesta es
10! 10!
10 · 9 · 8 · 7 · 6 · 5 = = = 151.200
4! (10 − 6)!
.

Ejemplo 2.4. ¿De cuántas maneras puede conformarse una comisión con 9
candidatos si debe haber un presidente, un vicepresidente, un tesorero y un
secretario?
Respuesta. El presidente puede ser cualquiera de los 9, y para cada una de
estas 9 opciones, hay 8 opciones para el vice, y ası́ siguiendo. Gráficamente:
9 · |{z}
|{z} 8 · |{z}
7 · |{z}
6
P V T S
Luego la respuesta es:
9! 9!
9·8·7·6= = = 3024
5! (9 − 4)!
.
Ahora damos la definición de permutación de n objetos tomados de a k y
a continuación el teorema que nos dice como calcularla.
Definición 2.1. Dados n objetos y dado k ∈ N0 tal que 0 ≤ k ≤ n, una
permutación de los n objetos tomados de a k (también llamada variación o
arreglo) es cualquier ordenación o disposición (ya sea en una lista o fila o
columna, por ejemplo) de k objetos tomados de los n dados.
Teorema 2.1. La cantidad de permutaciones de n objetos distintos tomados
de a k está dada por:
n!
= n · (n − 1) · (n − 2) · . . . · (n − k + 1)
(n − k)! | {z }
k factores

3
3. Permutaciones con repetición
Ejemplo 3.1. ¿Cuántas palabras se pueden formar permutando las letras de
la palabra CASACA?
Respuesta. Ahora hay 6 objetos a permutar pero de esos 6, hay 3 que son
idénticos entre sı́ (las tres A’s) y además hay otros dos tambien idénticos en-
tre sı́ (las dos C’s). Si considerásemos que las tres A’s son distintas, digamos
A1 , A2 , A3 , y que las dos C’s también son distintas, C1 , C2 por ejemplo, y si
quisiéramos contar entonces las permutaciones de la palabra C1 A1 SA2 C2 A3 ,
la respueta serı́a 6!, ya que estarı́amos contando las permutaciones de 6 ob-
jetos distintos.
Evidentemente, si respondiésemos 6! a nuestro problema original, estarı́amos
contando demás.
Por ejemplo, habrı́amos contando como distintas las palabras C1 A1 SA2 C2 A3
y C1 A3 SA1 C2 A2 . De hecho la palabra CASACA serı́a contada, en princi-
pio, tantas veces como permutaciones de A1 , A2 , A3 hay, o sea 3! = 6. Pero
además, también las permutaciones de las C’s producen la misma palabra,
por ejemplo C1 A3 SA1 C2 A2 y C2 A3 SA1 C1 A2 corresponden siempre a la única
palabra CASACA. Es decir cada una de las 3! palabras resultantes de per-
mutar las A’s tiene 2! = 2 versiones que surgen de permutar las dos C’s.
En definitiva, cada palabra que nos interesa (cuando las A’s y las C’s son
idénticas) está siendo contada 3! · 2! veces debido a las permutaciones de las
3 A’s y de las 2 C’s. De modo que la respuesta a nuestro problema es
6!
3! · 2!

Ejemplo 3.2. En una carrera internacional participan 9 corredores: 4 son

de Argentina, 3 son de Brasil y 2 son de Colombia. Se desea saber cuántos
resultados son posibles en cuanto a la clasificación de los paı́ses. (No importa
qué jugador sale primero sino que paı́s sale primero y lo mismo para cada
posicion hasta la novena.)
Respuesta. Contar lo que se nos pide, es lo mismo que contar cuántas
palabras se pueden formar con 4 A’s, 3 B’s y 2 C’s. Por ejemplo, la palabra
ABAACCBBA corresponde al resultado: el primero argentino, el segundo
brasileño, tercero y cuarto argentinos, quinto y sexto colombianos, etc. Luego,
por lo visto en el ejemplo anterior podemos concluir que la respuestas es:
9!
4! · 3! · 2!

Ejemplo 3.3. En una biblioteca hay 6 ejemplares idénticos de un libro de

Matemática, 3 ejemplares idénticos de un libro de Fı́sica, 2 ejemplares idénti-
cos de un libro de Astronomı́a, 2 ejemplares idénticos de un libro de Geologı́a
y un único ejemplar de un libro de Quı́mica. ¿De cuántas maneras puede el
bibliotecario ubicar los 14 libros en un estante en el que caben todos?

4
Respuesta. Contar lo que se nos pide, es lo mismo que contar cuantas
palabras se pueden formar con 5 M ’s, 3 F ’s, 2 A’s, 2 G’s y una Q. Luego la
respuesta es:
14! 14!
=
6! · 3! · 2! · 2! · 1! 6! · 3! · 2! · 2!

Ejemplo 3.4. Se quiere conformar una junta, al estilo de la Primera Junta,

es decir con un presidente, dos secretarios y 5 vocales. Hay 8 candidatos. ¿De
cuántas maneras se puede armar la junta?

Respuesta. Contar las juntas posibles es lo mismo que contar las palabras
que pueden formarse con una P , dos S’s y cinco V ’s. En efecto, supongamos
que los candidatos son C1 , C2 , C3 , ... , C8 . Ordenemos a los candidatos
de una vez y para siempre en una fila donde el primero es C1 , el segundo
C2 , el tercero es C3 , ... , el octavo C8 . Entonces, por ejemplo la palabra
V SV V P V SV , según la representación:
C1 C2 C3 C4 C5 C6 C7 C8
V S V V P V S V
corresponde a la junta cuyo presidente es C5 , cuyos secretarios son C2 y C7
y cuyos vocales son el resto de los candidatos. Luego, la respuesta es:
8! 8!
=
5! · 2! · 1! 5! · 2!

Todos los ejemplo vistos hasta aquı́ se encuadran en el siguiente teorema.

Teorema 3.1. Sean n objetos particionados en h tipos de modo tal que ob-
jetos del mismo tipo se consideran indistinguibles (o idénticos). Supongamos
que hay n1 objetos de tipo T1 , n2 de tipo T2 , ... , nh de tipo Th de modo tal
Ph
que ni = n, entonces la cantidad de permutaciones de esos objetos es:
i=1

n!
n1 ! · n2 ! · . . . · nh !

Volviendo al Ejemplo 3.1, hay 6 objetos a permutar que están particiona-

dos en 3 tipos: tipo A, tipo C y tipo S y hay 3 objetos de tipo A (las 3
A’s), 2 objetos de tipo C (las 2 C’s) y un objeto de tipo S (la única S).

5
4. Palabras
Ejemplo 4.1. ¿Cuántas palabras de tres letras pueden formarse con las letras
del conjunto {A, B, C, D, E}? (Llamamos palabra a cualquier sucesión de
letras del conjunto y donde cualquier letra puede repetirse cualquier cantidad
de veces.)
Respuesta. Algunos ejemplos de las palabras que tenemos que contar son
ACD, ACC, CAC, DDD.
La cantidad de opciones que tenemos para la primera letra es 5, ya que
cualquiera de las letras puede ser la primera. Para cualquiera de estas 5
opciones, tenemos nuevamente 5 opciones para la segunda letra, ya que las
letras pueden repetirse. Luego hay 5·5 = 25 opciones para primera y segunda
letra. Para cada una de estas 25 opciones, tenemos otra vez 5 opciones para
la tercera letra.
La respuesta final es entonces 5 · 5 · 5 = 53 = 125. Y puede representarse ası́:

5
|{z} · |{z}
5 · |{z}
5
1a letra 2a letra 3a letra

Ejemplo 4.2. En una carrera internacional participan 3 paı́ses: Argentina,

Brasil y Colombia. Cada paı́s está representado por 7 corredores. Se desea
saber cuántos resultados son posibles en cuanto a la clasificación de los paı́ses,
teniendo en cuenta sólo los primeros 5 puestos. (No importa qué jugador sale
primero sino qué paı́s sale primero y lo mismo para cada posicion hasta la
quinta.)
Respuesta. Contar lo que se nos pide, es lo mismo que contar cuántas
palabras de 5 letras se pueden formar con las letras A,B y C. Por ejemplo, la
palabra ABAAC corresponde al resultado: el primero argentino, el segundo
brasileño, tercero y cuarto argentinos y quinto colombiano. Luego, razonando
como en el ejemplo anterior podemos concluir que la respuestas es:
3 · 3 · 3 · 3 · 3 = 35
Observar que hay suficientes corredores (7) de cada paı́s como para contem-
plar la posibilidad de que los 5 primeros sean del mismo paı́s.

Ejemplo 4.3. Un bibliotecario tiene 7 ejemplares idénticos de un libro de

Álgebra, 9 ejemplares idénticos de un libro de Biologı́a, 11 ejemplares idénti-
cos de un libro de Combinatoria y 6 ejemplares idénticos de un libro de Fı́sica.
¿De cuántas maneras puede colocar 6 libros en un estante?
Respuesta. Observemos que de cada libro hay al menos 6 ejemplares. En-
tonces el problema se reduce a construir palabras de 6 letras, con las letras
del conjunto {A, B, C, F }, por ejemplo. Luego la respuesta es:
4 · 4 · 4 · 4 · 4 · 4 = 46

6
Ejemplo 4.4. ¿Cuántos autos serán necesarios para que se agoten las patentes
que tienen dos letras seguidas de tres dı́gitos seguidos de dos letras? Tener
en cuenta que las letras posibles son 26, que los dı́gitos son 10 y que tanto
letras como dı́gitos pueden repetirse.
Tenemos que contar cuántas patentes pueden existir. El problema puede
representarse ası́:
26 · |{z}
|{z} 26 · |{z}
10 · |{z}10 · |{z}10 · |{z} 26 · |{z}
26
1a let. 2a let. 1o dı́g. 2o dı́g. 3o dı́g. 3a letra 4a let.
Luego la respuesta es 264 · 103 .

Ahora presentamos de manera general los conceptos subyacentes a los

ejemplo que acabamos de ver.

Definición 4.1. Decimos que un alfabeto es un conjunto de objetos arbitra-

rios a los que llamamos letras. Y llamamos palabra de longitud k a cualquier
sucesión de k letras, donde las letras pueden repetirse.

Teorema 4.1. La cantidad de palabras de longitud k que pueden formarse

con un alfabeto de n letras es nk .

5. Combinaciones o Subconjuntos
Hasta aquı́ el orden de los objetos de las permutaciones o de las letras
de las palabras era relevante (ABC y BAC, por ejemplo eran consideradas
permutaciones distintas, o bien ACA y AAC eran consideradas palabras dis-
tintas). Ahora no nos interesará el orden, sino qué elementos aparecen en
nuestra lista de objetos. Las disposiciones ABC y BCA serán consideradas
como la misma elección de letras (se eligen las letras A, B y C en ambos
casos), mientras que ABC y ABD serán consideradas distintas elecciones (la
letra C aparece en la primera pero no en la segunda). A tales diposiciones o
elecciones se las llama combinaciones.
Por ejemplo, todas las combinaciones de 3 elementos del conjunto de cinco
objetos {A, B, C, D, E} están dadas por:
ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE
Observación 5.1. Las combinaciones de k elementos de un conjunto da-
do de n elementos, se corresponden exactamente con los subconjuntos de k
elementos del conjunto en cuestión.
Por ejemplo, la combinación ABD del conjunto {A, B, C, D, E} se corres-
ponde con el subconjunto {A, B, D}. Esto se debe a que, ası́ como en las
combinaciones no importa el orden, del mismo modo, no interesa el orden
cuando se trata de conjuntos, ya que {A, B, D} = {B, D, A}, por ejemplo.
Es ası́ como contar combinaciones o subconjuntos se reduce al mismo
problema.

7
Ejemplo 5.1. ¿Cuántas combinaciones de 4 elementos del conjunto de 6 ele-
mentos {A, B, C, D, E, F } hay? O lo que es lo mismo, ¿cuántos subconjuntos
de 4 elementos tiene el conjunto {A, B, C, D, E, F }?
Respuesta. Si el orden interesase se tratarı́a de contar las permutaciones de
6 elementos tomados de a 4; llamemos P a este número y tendrı́amos:
6!
P =
(6 − 4)!
Pero si queremos contar las combinaciones este número es excesivo, ya que
cada combinación estarı́a siendo contadas muchas veces. Se estarı́an contan-
do, por ejemplo ABCD y BACD como distintas, cuando en realidad son
la misma combinación. De hecho, cada combinación se está contando tantas
veces como permutaciones se pueden hacer con las 4 letras que la compo-
nen, es decir cada combinación se cuenta 4! veces y entonces el número de
combinaciones será P/4!. La respuesta entonces es:
6! 6! 6·5
= = = 15
4! · (6 − 4)! 4! · 2! 2

En lo que sigue expresiones de esta forma aparecerán a menudo, por ello

les daremos un nombre especial y usaremos una notación simplificada para
representarlas.
Definición 5.1.
Sean n ∈ N0 , k ∈ N0 tal que k ≤ n, definimos el número
combinatorio nk ası́:  
n n!
=
k k! · (n − k)!
 
6
Usando esta notación, la respuesta del ejemplo anterior serı́a pues:
4
 
6 6!
=
4 4! · (6 − 4)!

El modo en el que hemos resuelto el ejemplo anterior puede generalizarse a

conjuntos con cualquier cantidad de elementos. Y entonces podemos enunciar
el teorema siguiente.

Teorema 5.1. La cantidad de subconjuntos (o de combinaciones)  de 

k ele-
n
mentos de un conjunto de n elementos es el número combinatorio .
k

Observación 5.2. Algunas (de las muchas) propiedades de los números com-
binatorios son:
       
n n n n
a) = =1 b) = =n
0 n 1 n−1
         
n n n n n+1
c) = d) + =
k n−k k k−1 k
Es un buen ejercicio verificar las identidades anteriores usando la definición
de número combinatorio.

8
 Veamos otros ejemplos de problemas que se resuelven con combinaciones
o subconjuntos.

Ejemplo 5.2. ¿De cuántas maneras se puede elegir una comisión de 5 per-
sonas de un curso de 20 estudiantes para ocuparse de la organización de un
partido de fútbol?

Respuesta. Dado que sólo nos interesa considerar el grupo de cinco personas
sin ningún orden interno, se trata de un problema de combinaciones. O bien,
se puede pensar simplemente que queremos contar cuántos subconjuntos de
5 estudiantes se pueden formar a partir del conjunto de los 20 estudiantes
del curso. Luego, la respuesta es:
 
20 20! 20!
= =
5 5! · (20 − 5)! 5! · 15!

Ejemplo 5.3. ¿De cuántas maneras puedo elegir 4 libros de los 7 que hay
en la mesa para guardarlos en la mochila?

Respuesta. Dado que no habrá orden dentro de la mochila la respuesta es:

 
7 7! 7!
= =
4 4! · (7 − 4)! 4! · 3!

Ejemplo 5.4. En un curso de 30 alumnos se desea elegir 11 para formar

un equipo de fútbol y 5 para armar un equipo de básquet. Decir de cuántas
maneras puede hacerse la elección si

1. nadie puede estar en los dos equipos.

2. cualquiera puede estar en ambos equipos.

Respuesta.

1. Hay 30


11
maneras de elegir el equipo de fútbol y para cada una de estas
elecciones, hay que elegir el equipo de básquet entre los 19 restantes,
ya que nadie puede estar en ambos equipos. Luego la repuesta es:
   
30 19
·
11 5

2. Hay 30


11
maneras de elegir el equipo de fútbol y para cada una de estas
elecciones, hay que elegir el equipo de básquet otra vez entre los 30, ya
que ahora no hay restricciones para estar en ambos equipos. Luego la
respuesta es:    
30 30
·
11 5

9
6. Cajas y bolitas
Un problema interesante y que resulta útil para responder a un problema
que nos plantearemos en la próxima sección es el siguiente.
Problema 1. ¿De cuántas maneras se pueden poner k objetos indistinguibles
(bolitas idénticas, por ejemplo) en n cajas distintas (numeradas de 1 a n, por
ejemplo)?
Antes de presentar la solución del problema es importante entender qué se
nos pide. Consideremos un ejemplo concreto. Supongamos que tenemos 7
bolitas idénticas y tenemos 3 cajas. Una disposición posible es:

••
|{z} •| •{z• •} •
|{z}
Caja 1 Caja 2 Caja 3
Esta disposición corresponde a la situación en que hay 2 bolitas en la primera
caja, 4 en la segunda y una en la tercera.
Otra disposición posible podrı́a ser:

•| {z
• •} |{z} •| •{z• •}
Caja 1 Caja 2 Caja 3
Aquı́ tenemos 3 bolitas en la primera, ninguna en la segunda y 4 en la tercera.
Lo que nos pide el problema es el total de situaciones posibles, desde 7
en la primera caja y nada en las otras dos hasta la situción en que no hay
nada en las dos primeras cajas y 7 en la última.
Podemos razonar del siguiente modo. Elegimos dos sı́mbolos: el sı́mbolo
• para representar una bolita y el sı́mbolo | para representar un separador
entre dos cajas. Con estos dos sı́mbolos podemos representar todas las situa-
ciones posibles. Por ejemplo la primera situación que hemos representado
más arriba, ahora se representa ası́:

•• | •••• | •
Y la segunda situación ahora se representa ası́:

•••| | ••••
Lo que debemos contar entonces es cuántas “palabras” de 9 “letras” pode-
mos formar con 7 “letras” • y 2 “letras” |. Es exactamente análogo al prob-
lema de CASACA y la respuesta entonces es
 
9! 9! 9
= =
7! · 2! 7! · (9 − 7)! 7
También podrı́amos haber razonado ası́: de los 9 espacios disponibles
para poner • o bien | tenemos que elegir 7 donde poner las bolitas (los
2 espacios de los separadores quedan automáticamente determinados), y de
9


allı́ el número combinatorio 7 .

10
 Observemos que la cantidad de | que usamos es la cantidad de cajas
menos una. Esto es ası́ ya que los | son separadores de cajas.
Observemos finalmente que 9 es la cantidad de bolitas (7) más la cantidad
de cajas (3) menos 1. Podemos expresar entonces la respuesta al problema
como el siguiente teorema.

Teorema 6.1. La cantidad de maneras

 de ubicar k objetos indistinguibles
k+n−1
en n cajas distintas es .
k

Veamos ahora una variente del Problema 1 en la que no se admitirán

cajas vacı́as.
Problema 2. ¿De cuántas maneras se pueden poner k objetos indistinguibles
en n cajas distintas, si ninguna caja debe estar vacı́a?
Es claro que el problema tiene solución si y sólo si k ≥ n.
Para asegurarnos que ninguna caja quede vacı́a, pongamos un objeto en
cada caja y entonces nos quedan k − n objetos por distribuir. Y ahora la
distribución podemos hacerla de cualquier modo.
Por lo tanto el problema se reduce a distribuir k − n objetos en n cajas. Por
el teorema anterior, esto puede hacerse del siguiente número de maneras:
       
(k − n) + n − 1 k−1 k−1 k−1
= = =
k−n k−n (k − 1) − (k − n) n−1

La segunda igualdad se justifica por la Observación 5.2.c. Podemos enunciar

entonces el siguiente teorema.

Teorema 6.2. Sea k ≥ n, la cantidad de maneras de ubicar k objetos  indis-


k−1
tinguibles en n cajas distintas de modo que no haya cajas vacı́as es .
n−1

7. Multiconjuntos
Un multiconjunto es un conjunto que admite elementos repetidos.
Dos multiconjuntos son considerados iguales cuando y sólo cuando, además
de tener los mismos elementos, cada uno de ellos aparece la misma cantidad
de veces.
Para diferenciar los multiconjuntos de los conjuntos, notaremos los mul-
ticonjuntos con llaves dobles.
Por ejemplo, valen las siguientes igualdades:

{{a, a, b, b, b, c}} = {{a, b, a, b, c, b}} = {{c, b, b, b, a, a}}

11
 Decimos que {{a, a, b, b, b, c}} es un multiconjunto de 6 (SEIS!!) elementos,
ya que cada elemento se cuenta tantas veces como la cantidad de ocurrencias
que tiene en el multiconjunto.
Por otra parte, {{a, a, b, b, b, c}} 6= {{b, a, b, a, c}}, ya que, si bien los elemntos
de ambos son a, b, c, tenemos 3 ocurrencias de b en el primer multiconjunto y
sólo 2 ocurrencias de b en el segundo. Observar que la igualdad de conjuntos
{a, a, b, b, b, c} = {b, a, b, a, c} es válida.
También vale que {{c, b, b, b, a, a}} 6= {{a, b, b, b, a, c, d}}, porque aunque a,
b, c aparecen en ambos multiconjuntos igual cantidad de veces cada uno, en
el segundo multiconjunto aparece d, que no es elemento del primer multicon-
junto.
Problema 3. ¿Cuántos multiconjuntos de k elementos pueden construirse a
partir de un conjunto de n elementos distintos?
Para fijar ideas supongamos que tenemos un conjunto de 3 elementos, di-
gamos el conjunto {a, b, c} y queremos saber cuántos multiconjuntos de 7
elementos pueden construirse a partir de dicho conjunto.
Por ejemplo, debemos computar multiconjuntos tales como
{{a, a, b, b, b, c, c}}, {{a, a, a, a, b, b, b}}, {{b, b, b, b, b, b, b}}
Podemos pensar que tenemos 3 cajas rotuladas con “a”, “b”, “c”, y entonces
los tres multiconjuntos recién mencionados se corresponden con las siguientes
distribuciones de 7 bolitas en esas 3 cajas. En efecto, la distribución:
••
|{z} •|{z}
•• ••
|{z}
Caja “a” Caja “b” Caja “c”
se corresponde con el multiconjunto {{a, a, b, b, b, c, c}} ya que hay 2 bolitas en
la caja “a”, 3 en la caja “b” y 2 en la caja “c”.
La distribución:
•| •{z• •} •| {z
• •} |{z}
Caja “a” Caja “b” Caja “c”
se corresponde con el multiconjunto {{a, a, a, a, b, b, b}} ya que hay 4 bolitas
en la caja “a”, 3 en la caja “b” y ninguna en la caja “c”.
La distribución:

|{z} •| • • {z
• • • •} |{z}
Caja “a” Caja “b” Caja “c”
se corresponde con el multiconjunto {{b, b, b, b, b, b, b}} ya que no hay ninguna
bolita en la caja “a”, 7 en la caja “b” y ninguna en la caja “c”.
Vemos entonces que contar los multiconjuntos de 7 elementos que se
pueden armar a partir de un conjunto de 3 elementos (distintos) es lo mismo
que contar todas las distribuciones posibles de 7 bolitas en 3 cajas. Y eso
sabemos hacerlo gracias al Teorema 6.1:
   
7+3−1 9 9! 9·8
= = = = 36
7 7 7! · 2! 2

12
 A partir del razonamiento que acabamos de hacer, podemos responder a
la pregunta del Problema 3 con el siguiente teorema.

Teorema 7.1. La cantidad de multiconjuntos de k elementos que pueden

construirse a partir de un conjunto de n elementos (distintos) es:
 
k+n−1
k
Además este número coincide con las distintas maneras de ubicar k objetos
indistinguibles en n cajas distintas.

8. Ejemplo integrador
Veamos un ejemplo donde se combinan cuatro de los conseptos vistos en
esta unidad.
Ejemplo 8.1. Se organizó una rifa para recaudar fondos para un viaje de
egresados. Se vendieron 100 números a 100 participantes y son 5 los objetos
que se rifan. Se desea saber cuántos son los resultados posibles si
1. los objetos son distintos y sólo puede haber un premio para cada parti-
cipante.
2. los objetos son idénticos y sólo puede haber un premio para cada parti-
cipante.
3. los objetos son distintos y no hay restricción alguna respecto a la can-
tidad de premios por participante.
4. los objetos son idénticos y no hay restricción alguna respecto a la can-
tidad de premios por participante.
Supongamos que el sorteo se realiza colocando los 100 números en una
bolsa. En el caso en que sólo puede haber un premio por cada participante,
cada vez que se extrae un número de la bolsa, dicho número se descarta. En el
caso en que no hay restricción a la cantidad de premios por participante, cada
vez que se extrae un número de la bolsa, dicho número vuelve a introducirse
en la bolsa, de modo que puede volver a salir en alguna extracción posterior.
Solución al item 1. Cualquiera de los 100 participantes puede obtener el
primer premio, de modo que el segundo puede ser para cualquiera de los 99
restantes y ası́ siguiendo. Se trata de contar permutaciones de 100 tomadas
de a 5 y la respuesta es:
100! 100!
= = 100 · 99 · 98 · 97 · 96
(100 − 5)! 95!
Solución al item 2. Se trata de elegir de entre los cien participantes, quienes
serán los premiados. El orden no importa ya que los premios son todos iguales.
Luegp la respuesta es:
 
100 100! 100 · 99 · 98 · 97 · 96
= =
5 5! · (100 − 5)! 120

13
Solución al item 3. Cualquiera de los 100 participantes puede obtener el
primer premio, el segundo premio también puede llevárselo cualquiera de los
100, ya que no hay restricción a la cantidad de premios por participante, y
ası́ siguiendo. Se concluye que la respuesta es:
100 · 100 · 100 · 100 · 100 = 1005 = 10.000.000.000
Solución al item 4. Ahora como los objetos son idénticos y no hay restric-
ción a la cantidad de premios por participante, podemos pensar que cada
participante es como una caja dentro de la cual pueden ponerse de 0 a 5 pre-
mios. Se trata entonces de distribuir 5 objetos indistinguibles en 100 cajas y
la repuesta es:
   
5 + 100 − 1 104 104! 104! 104 · 103 · 102 · 101 · 100
= = = =
5 5 5! · (104 − 5)! 5! · 99! 120

El ejemplo que acabamos de ver ilustra cada uno de los cuatro casos
contemplados en la segunda tabla de la sección siguiente.

9. Resumen
Resumimos todo lo visto en esta unidad en la tabla siguiente:

n objetos distintos n!
Permutaciones
n!
n objetos distintos tomados de a k (n−k)!

h
P n!
ni letras de tipo Ti , con ni = n n1 ! n2 ! ··· nh !
i=1
Palabras

Palabras de longitud k
nk
con un alfabeto de n letras

Subconjuntos de k elementos n


de un conjunto de n elementos k
Conjuntos
Multiconjuntos de k elementos k+n−1


tomados de un conjunto de n elementos k

14
En cuanto a los distintos tipos de elecciones dependiendo de

1. si se consideran repeticiones o no

2. si se tiene en cuenta el orden o no

la tabla siguiente resume las distintas situaciones.

Elegir k de n importa el orden no importa el orden

n! n


Sin repeticiones (n−k)! k

k+n−1


k
Con repeticiones n k

15