Laboratorio de Estructuras Discretas Página: 1

UNIVERSIDAD CATÓLICA DE SANTA MARÍA

ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS

Laboratorio N° 05.2

COMBINACIONES EN PYTHON

I
OBJETIVOS
Entender las características matemáticas y conceptuales de las combinaciones
Utilizar principios básicos de conteo para calcular combinaciones
Aplicar algoritmos para generar combinaciones.

II
TEMAS A TRATAR
Combinaciones sin repetición
Combinaciones con repetición
Algoritmos de generación de Combinaciones y Permutaciones
Ejercicios

III
MARCO TEÓRICO

Combinaciones sin Repetición

Una selección de objetos que no toma en cuenta el orden se llama combinación.

Definición 1: Dado un conjunto X = {x1 , . . . , xn} que contiene n elementos (diferentes):

a) Una combinación r de X es una selección no ordenada de r elementos de X (es decir, un

subconjunto de X de r elementos).
𝑛
b) El número de combinaciones r de un conjunto de n elementos distintos se denota por C(n, r) o ( )
𝑟

Por ejemplo: ¿Cuántos tonos y colores distintos puede formar mezclando iguales cantiodades de 3
colors diferentes tomados de una paleta de 6 (Rojo, Azul, Verde, Naranja, Blanco)?

Para resolver este problema no debe tomarse en cuenta el orden. (Por ejemplo, no hay diferencia si se
elige Blanco, Azul y Naranja o Naranja, Azul y Blanco, el tono y color luego de mezclarlos será el
mismo).

Con sólo listar las posibilidades, se ve que existen 10 maneras de elegir los tres colores:

VBR, VBA, VRA, BRA, VBN, VRN, BRN, VAN, BAN, RAN.

Karim Guevara Puente de la Vega – Carlo Corrales Delgado Lab. 05.2

 Laboratorio de Estructuras Discretas Página: 2

El número de maneras en que se pueden elegir los 3 colores de un total de 5 es C(5, 3), el número de
combinaciones de 3 de cinco elementos. Se ha encontrado que:
C(5, 3) = 10

Ahora se derivará la fórmula para C(n, r) contando el número de permutaciones r de un conjunto de n

elementos de dos maneras. La primera simplemente usa la fórmula P(n, r). La segunda manera de contar
el número de permutaciones de un conjunto de n elementos implica C(n, r). Igualar los dos valores nos
permitirá obtener una fórmula para C(n, r).

Podemos construir permutaciones r de un conjunto X de n elementos en dos pasos sucesivos: primero,

elegimos una combinación r de X (un subconjunto no ordenado de r elementos); segundo, se ordena.
Por ejemplo, para construir una permutación de 2 de {a, b, c, d}, primero elegimos una combinación de
2 y después lo ordenamos. A continuación se muestra cómo se obtienen todas las permutaciones 2 de
{a, b, c, d} de esta manera.

Figura No 1: Permutaciones de 2 elementos de {a, b, c, d}

El principio de multiplicación dice que el número de permutaciones r es el producto del número de

combinaciones r por el número de ordenamientos de r elementos; es decir,

P(n, r) = C(n, r) . r!

Por lo tanto,

𝑃(𝑛, 𝑟)
𝐶(𝑛, 𝑟) =
𝑟!

Teorema: El número de combinaciones r de un conjunto de n objetos distintos es

𝑃(𝑛,𝑟) 𝑛(𝑛−1)…(𝑛−𝑟+1) 𝑛!
𝐶 (𝑛, 𝑟) = 𝑟!
= 𝑟!
= (𝑛−𝑟)!𝑟! r  n

Ejemplos

1. ¿De cuántas maneras se puede seleccionar un comité de cuatro a partir de un grupo de 10 personas
diferentes?
Como un comité es un grupo no ordenado de personas, la respuesta es:

10 . 9 . 8 . 7
𝐶(10, 4) = = 210
4!

2. ¿De cuántas maneras se puede seleccionar un comité de dos mujeres y tres hombres de un grupo de
cinco mujeres y seis hombres?
• Las dos mujeres se pueden elegir de

Karim Guevara Puente de la Vega – Carlo Corrales Delgado Lab. 05.2

 Laboratorio de Estructuras Discretas Página: 3

C(5, 2) = 10 maneras
• Y que los tres hombres se pueden elegir de
C(6, 3) = 20 maneras

El comité se construye en dos pasos sucesivos: se elige a las mujeres; se elige a los hombres.
Por el principio de la multiplicación, el número total de comités es:
C(5,2) . C(6,3) = 10 · 20 = 200

3. Una baraja común de 52 cartas consiste en cuatro palos: tréboles, diamantes, corazones y espadas
con 13 denominaciones cada uno: as, de 2 a 10, jack, reina y rey.

1. ¿Cuántas manos de póquer (sin ordenar) de cinco cartas, seleccionadas de una baraja común de
52 cartas, existen?
La respuesta está dada por la fórmula de las combinaciones
C(52, 5) = 2,598,960

2. ¿Cuántas manos de póquer contienen cartas todas del mismo palo?

Una mano en la que todas las cartas son del mismo palo se puede construir en dos pasos
sucesivos: seleccionamos un palo; seleccionamos cinco cartas del palo elegido.
• El primer paso se puede realizar de cuatro maneras
• Yel segundo de C(13, 5) maneras.

Por el principio de la multiplicación, la respuesta es

4 * C(13, 5) = 5148

3. ¿Cuántas manos de póquer contienen tres cartas de una denominación y dos de una segunda
denominación?
Una mano que contiene tres cartas de una denominación y dos de otra se puede construir en
cuatro pasos sucesivos: seleccionamos la primera denominación; seleccionamos la segunda
denominación; seleccionamos tres cartas de la primera denominación; seleccionamos dos cartas
de la segunda denominación.
• La primera denominación se puede elegir de 13 maneras.
• Una vez elegida, se puede seleccionar la segunda denominación de 12 maneras.
• Se pueden elegir tres cartas de la primera denominación de C(4, 3) maneras
• Y se pueden seleccionar dos cartas de la segunda denominación de C(4, 2) maneras.

Por el principio de la multiplicación, la respuesta es:

13 · 12 ·C(4, 3) ·C(4, 2) = 3744

Combinaciones con Repetición

El número de maneras de seleccionar r objetos a partir de n objetos distintos, con selecciones repetidas
es:

Por lo tanto, el número de combinaciones de n objetos tomados de r en r, con repeticiones, es:

C(n+r-1, r)

Ejemplos:

1. Cuando se lanzan tres dados, el número de resultados diferentes es:

C(6+3-1,3) = C(8,3) = 56

Karim Guevara Puente de la Vega – Carlo Corrales Delgado Lab. 05.2

Laboratorio de Estructuras Discretas Página: 4

Debido a que lanzar tres dados equivale a seleccionar tres de los seis números 1,2,3,4,5,6 con
repeticiones permitidas.

2. Una tienda ofrece 20 tipos de donas. Si suponemos que al menos hay una docena de cada tipo
cuando entramos a la tienda, podemos elegir una docena de donas de:

C(20+12-1,12) = C(31,12) = 141,120,525 formas

3. ¿De cuántas formas se pueden distribuir tres manzanas y seis naranjas entre cuatro niños, de modo
que cada niño reciba al menos una manzana?
• Al dar a cada niño una manzana, se tiene C(4+3–1,3) = 20 formas de distribuir las tres
manzanas
• y C(4+6–1,6) = 84 formas de distribuir las seis naranjas.

Por la regla del producto, hay 20 * 84 = 1680 formas de distribuir la fruta en las condiciones
establecidas.

4. Determínense todas las soluciones enteras de la ecuación

𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 7, donde 𝑥𝑖 ≥ 0 para toda 1 ≤ 𝑖 ≤ 4

Una posible interpretación sería: Se distribuyen siete centavos (objetos idénticos) entre cuatro niños
(destinatarios distintos). Si x1=3, x2=3, x3=0, x4=1 se puede ver como si se dieron tres centavos a
cada uno de los dos primeros niños, nada al tercero y el último centavo al cuarto.

Bajo esta interpretación, se observa que cada solución entera no negativa de la ecuación
corresponde a una selección con repetición, de tamaño 7 (los centavos idénticos) de una colección
de tamaño 4 (los niños distintos), de modo que hay:

C(4+7–1, 7) = 120 soluciones.

5. ¿Cuántas veces es ejecutada la proposición writeln en el siguiente segmento del programa?

Cualquier i, j, k satisface 1 ≤ k ≤ j ≤ i ≤ 20
Esto es, seleccionar 3 números, con repetición, de 20 entre números:

C(20+3-1,3) = C(22,3) = 1540 veces

RESUMEN

Karim Guevara Puente de la Vega – Carlo Corrales Delgado Lab. 05.2

 Laboratorio de Estructuras Discretas Página: 5

Algoritmos en Python para generar Combinaciones y Permutaciones

1. Algoritmos para Combinaciones

def combinacion(r, n):

s = [0]
for i in range(1,r+1):
s.append(i)
print (s[1:r+1])
for i in range(2, combina(n,r)+1):
m = r
val_min = n
while (s[m] == val_min):
m = m – 1
val_min = val_min – 1
s[m] = s[m] + 1
for j in range(m+1, r+1):
s[j] = s[j-1] + 1
print (s[1:r+1])

Ejemplo de combinación 2 de 5 (1,2,3,4,5):

2. Algoritmos para generar Permutaciones

def permutacion(n):
s = [0]
for i in range(1,n+1):
s.append(i)
print (s[1:n+1])
for i in range(2, fact(n)+1):
m = n - 1
while (s[m] > s[m+1]):
m = m – 1
k = n
while (s[m] > s[k):
k = k -1
s[m], s[k] = s[k], s[m]
p = m + 1
q = n
while (p < q):
s[p], s[q] = s[q], s[p]
p = p + 1
q = q - 1
print (s[1:n+1])

Karim Guevara Puente de la Vega – Carlo Corrales Delgado Lab. 05.2

Laboratorio de Estructuras Discretas Página: 6

Ejemplo de permutación n=4 (1,2,3,4):

IV
ACTIVIDADES

1. Desarrollar los siguientes ejercicios de combinaciones:

1.1. En un examen de Estructuras Discretas, un alumno debe responder a ocho preguntas
cualesquiera de un cuestionario de diez ¿De cuántas maneras el estudiante puede responder el
examen?
1.2. En el ejercicio anterior, si el estudiante tiene que responder a cuatro preguntas de las cinco
primeras y a cuatro de las cinco últimas ¿De cuántas maneras el estudiante puede responder el
examen?
1.3. ¿Cuántas cadenas de 8 bits contienen 3 ceros seguidos y 5 unos?
1.4. Siendo X = {a, b, c, d}. Liste las combinaciones de 3 de X.
1.5. Una moneda se lanza 10 veces
a) ¿Cuántos resultados tienen exactamente tres caras?
b) ¿Cuántos resultados tienen a lo sumo tres caras?
1.6. ¿De cuántas formas es posible distribuir 10 monedas (idénticas) entre cinco niños si:
a) no hay restricciones?
b) cada niño recibe al menos una moneda?
c) el niño mayor recibe al menos dos monedas?

2. Utilizar el módulo itertools de Python para hallar las combinaciones

2.1. Mostrar combinaciones 2 de los elementos A, B, C y D
Desde el terminal:

Karim Guevara Puente de la Vega – Carlo Corrales Delgado Lab. 05.2

Laboratorio de Estructuras Discretas Página: 7

2.2. Mostrar las combinaciones 2 de los elementos 1, 2, y 3

3. Pruebe el algoritmo combinaciones del marco teórico, analice los resultados y

compare con los devueltos por el módulo itertools.
3.1. Combinaciones cuando n = 6 y r = 3.
3.2. Combinaciones cuando n = 6 y r = 2.
3.3. Combinaciones cuando n = 7 y r = 5.

4. Encontrar fuentes bibliográficas, libros y tutoriales sobre el tema. Buscar más

ejemplos. Leerlos y aprender de ellos.

V
EJERCICIOS
1. Implemente un algoritmo para calcular las combinaciones r de n elementos C(n,r) siendo n y r
números enteros donde 0 ≤ r ≤ n
2. Implemente un algoritmo que enumere todas las selecciones de tamaño 2 de los objetos
1,2,3,4,5,6
3. Implemente un algoritmo que halle el número de disposiciones de las letras de un texto
introducido. Por ejemplo si el texto es TALLAHASSEE, el número de disposiciones de las letras
son:
11!
= 831,600 formas
3!∙2!∙2!∙2!∙1!∙1!

4. Implemente un algoritmo que halle el número de disposiciones de las letras de TALLAHASSEE,

que no tengan letras A adyacentes
Cuando no se toma en cuenta las letras A, existen 5040 formas (8!/2!2!2!1!1!) de ordenar las
letras restantes.
Si solo es posible colocar las tres letras A en nueve posiciones para no ser adyacentes

9
Tres de estas posiciones se pueden seleccionar de ( ) = 84 formas
3
Como esto también es posible para las 5039 ordenaciones restantes, por la regla del producto,
hay 5040 x 84 = 423, 360 disposiciones de las letras de TALLAHASSEE sin letras A
consecutivas
5. En el algoritmo anterior que el usuario especifique que letra del texto introducido no debe estar
consecutiva
6. Implemente un algoritmo para calcular las combinaciones de n objetos tomados de r en r, con
repeticiones: C(n+r-1, r)

Karim Guevara Puente de la Vega – Carlo Corrales Delgado Lab. 05.2

Laboratorio de Estructuras Discretas Página: 8

7. ¿Cuántas veces se ejecuta la sentencia Writeln en el siguiente segmento de programa? Siendo i,

j, k y m variables enteras

VI
CUESTIONARIO

1. Cuáles son los tipos de combinaciones? ¿En qué consisten?

2. ¿En qué consiste el teorema del binomio? De ejemplos
3. ¿En qué se diferencian permutaciones y combinaciones?

VII
BIBLIOGRAFÍA Y MATERIAL DE REFERENCIA

• Tutorial de Python 3.6.3 Documentation. Disponible en:

https://tutorial.python.org.ar/en/latest/
• JOHNSONBAUGH, R. Matemáticas Discretas. México. Pearson. 6ta Ed. 2005
• https://ccc.inaoep.mx/~villasen/CursoMatDiscretas/PrincipiosConteo.pdf

Karim Guevara Puente de la Vega – Carlo Corrales Delgado Lab. 05.2