PDF de programación - Permutaciones y Combinaciones

Matemáticas Discretas

L. Enrique Sucar

INAOE

Permutaciones y Combinaciones

Contenido

• Introducción
• Reglas de la suma y el producto
• Permutaciones
• Combinaciones
• Generación de permutaciones
• Teorema del Binomio

© E. Sucar, PGM: 2 Probabilidad

2

Introducción

• En ocasiones, interesa saber cuántas diferentes
permutaciones/combinaciones de elementos se
pueden generar a partir de cierto conjunto, por
ejemplo:
– Cuántos comités diferentes de 3 personas puede haber a

partir de un grupo de 10 individuos?

– De cuántas diferentes maneras pueden repartirse 5

cartas a partir de 52 cartas (pokar)?

– De una urna con 10 bolas, 6 rojas y 4 negras, cuántas

formas diferentes existen al extraer 4 bolas, asumiendo
que cada vez que se saca una, se regresa a la urna?

© E. Sucar, PGM: 2 Probabilidad

3

Introducción

• En esta sesión veremos la teoría matemática

que nos permite hacer éstos cálculos, así
como algunos ejemplos de aplicación

© E. Sucar, PGM: 2 Probabilidad

4

Experimento

• Un proceso físico que tiene un número de posibles

resultados
• Ejemplos:

– Tirar una moneda y observar que cara queda arriba
– Tirar n monedas y observar las caras que quedan arriba

en cada moneda

– Sacar m pelotas de una caja con n pelotas
– Seleccionar 3 miembros para un comité de un grupo de

– De n personas que fuman, observar cuántas tienen

n personas

cáncer

© E. Sucar, PGM: 2 Probabilidad

5

Regla del Producto

• Si hacemos 2 experimentos, uno con n

posibles resultados, y otro con m posibles
resultados, el número total de resultados al
realizar ambos experimentos es m x n

• Ejemplos:

– A partir de 10 senadores y 10 diputados se va a hacer
un comité con 3 senadores y 4 diputados, de cuántas
maneras diferentes se puede conformar dicho comité

© E. Sucar, PGM: 2 Probabilidad

6

Regla de la Suma

• Si hacemos 2 experimentos, uno con n posibles
resultados, y otro con m posibles resultados, el
número total de resultados al realizar
exactamente uno de los experimentos es m + n

• Ejemplos:

– A partir de 10 senadores y 10 diputados se va a hacer un

comité con 3 miembros, todos ellos diputados o senadores,
de cuántas formas se puede conformar el comité?

© E. Sucar, PGM: 2 Probabilidad

7

Permutaciones

• Dados n objetos, queremos obtener las

diferentes formas de ordenar r de éstos objetos
• Por ejemplo, dada las letras a,b,c, de cuántas

formas podemos arreglar 2 de ellas:

ab, ba, ac, ca, bc, cb

• Esto se conoce como las permutaciones de r de

n, P(n, r)

© E. Sucar, PGM: 2 Probabilidad

8

Permutaciones

© E. Sucar, PGM: 2 Probabilidad

9

Permutaciones

© E. Sucar, PGM: 2 Probabilidad

10

Permutaciones

• El número de permutaciones se obtiene de

la siguiente manera:

P(n,r) = n! / (n-r)!

• Donde n! es el factorial de n, definido

como:

n! = n (n-1) (n-2) …. x 2 x 1

© E. Sucar, PGM: 2 Probabilidad

11

Ejemplos:

• De cuántas maneras se pueden colocar 3 pelotas
diferentes (azul, verde, rojas) en 10 cajas, si en
cada caja sólo cabe una pelota?

• Si hay 7 oficinas, y queremos asignarle una

oficina a cada uno de 4 estudiantes, de cuántas
formas se pueden asignar las oficinas?

• Cuántos números de 3 dígitos se pueden escribir

de forma que no se repitan dígitos?

© E. Sucar, PGM: 2 Probabilidad

12

Permutaciones – Generalización

• Ahora consideramos que tenemos t clases
de objetos, de forma que los de una clase
son indistinguibles entre sí

• Cómo podemos ordenar n objetos, con q1
del tipo 1, q2 del tipo 2, …, qt del tipo t?

• Por ejemplo, 3 letras, 2 a’s y 1 b:

aab, aba, baa

© E. Sucar, PGM: 2 Probabilidad

13

Permutaciones – Generalización

• Esto lo podemos calcular de la siguiente manera:

n! / (q1! q2! … qt!)

• Ejemplos:

– Para el código morse (puntos y rayas), cuántos mensajes

se pueden hacer con dos puntos y tres rayas?

– Hay 10 oficinas, 2 las va a explorar el robot 1, 5 el robot
2, y 3 el robot 3, de cuántas formas diferentes se pueden
organizar los robots para explorar las oficinas?

© E. Sucar, PGM: 2 Probabilidad

14

Combinaciones

• Dado que tenemos n objetos, de cuántas

formas podemos seleccionar r de éstos (sin
importar el orden)?

• Por ejemplo, tenemos 3 pelotas, una roja,

una verde y otra azul, de cuántas formas se
pueden sacar 2 pelotas:
– (roja, verde), (roja, azul), (verde azul)

© E. Sucar, PGM: 2 Probabilidad

15

Combinaciones

© E. Sucar, PGM: 2 Probabilidad

16

Combinaciones

© E. Sucar, PGM: 2 Probabilidad

17

Combinaciones

• Esto son las combinaciones r de n, o C(n, r), y se

obtienen con la siguiente expresión:
C(n,r) = n! / r! (n-r)!

• Ejemplos:

– De cuántas formas se pueden colocar 3 pelotas (iguales)

en 10 cajas, cada caja puede tener máximo una pelota?
– Cuántos números binarios de 5 dígitos con 3 unos se

pueden tener?

– Cuántos comités distintos de 3 personas podría haber en

este grupo de 60 estudiantes?

© E. Sucar, PGM: 2 Probabilidad

18

Generación de permutaciones

• Cómo generar todas las posibles permutaciones de

n objetos?

• Si son pocos, lo podemos hacer “a mano”:

– abc
– acb
– bac
– bca
– cab
– cba

© E. Sucar, PGM: 2 Probabilidad

19

Generación de permutaciones

• Si son muchos, ya no es tan fácil!
• Para ello requerimos de un algoritmo para

generar las permutaciones

• El algoritmo se basa en asignarle un

número consecutivo a cada objeto (1,2, …),
de forma que las permutaciones sigan un
orden, llamado orden lexicográfico

© E. Sucar, PGM: 2 Probabilidad

20

Orden lexicográfico

• En el ejemplo, si hacemos a=1, b=2, c=3,

entonces:
– abc
– acb
– bac
– bca
– cab
– cba

123
132
213
231
312
321

• Están ordenadas lexicográficamente

© E. Sucar, PGM: 2 Probabilidad

21

Algoritmo

• Iniciar con la secuencia “menor” de acuerdo al

orden (1,2,…, n)

• Dada la secuencia a [a1,a2,…am], generar la
siguiente secuencia b [b1,b2, …,bm] tal que:
– De izquierda a derecha, ai=bi, hasta el máximo posible

valor m

– Sustituir el valor bm, por el valor más pequeño aj, j>m,

que sea mayor a bm

– Ordenar los demás elementos de acuerdo al orden

• Repetir 2 hasta alcanzar la secuencia “mayor”

lexicográfico

(n, n-1, …, 1)

© E. Sucar, PGM: 2 Probabilidad

22

Ejemplo

• Dado el elemento:

– 124653

• El valor m=3

– 124…

• Por lo que el elemento 4 se sustituye por el 5 (el

menor de 635 que es mayor a 4):
– 125…

• Agregando el resto de los elementos:

– 125346

© E. Sucar, PGM: 2 Probabilidad

23

Permutaciones de r elementos

• El algoritmo anterior se extiende

directamente para generar las
permutaciones de r elementos a partir de n
objetos

© E. Sucar, PGM: 2 Probabilidad

24

Teorema del Binomio

• Binomio al cuadrado:

(a + b)2 = (a + b)(a + b) = a2 + ab + ba + b2

= a2 + 2ab + b2

• Binomio al cubo:

(a + b)3 = a3 + 3a2b + 3ab2 + b3

• En general:

(a + b)n = ?

© E. Sucar, PGM: 2 Probabilidad

25

Teorema de Binomio

• En general, cada término surge de elegir a

en n-k factores y b en k factores

• Por ejemplo, para el binomio al cubo:

aba, aab, baa 3a2b

C(3,1) a2b = 3a2b

• En general, cada término tiene como

coeficiente C(n, k)

© E. Sucar, PGM: 2 Probabilidad

26

Teorema de Binomio

• Así, un binomio a la n se puede escribir

como:
(a + b)n = C(n,0) anb0 + C(n,1) an-1b1 + … +

C(n,n) a0bn

• Teorema del binomio:

(a + b)n = Σk C(n,k) an-kbk

© E. Sucar, PGM: 2 Probabilidad

27

Triángulo de Pascal

• Una forma de obtener los coeficientes es

mediante el triángulo de Pascal

• El triángulo tiene 1’s en las orillas, y todos
los números interiores son la suma de los 2
de arriba

© E. Sucar, PGM: 2 Probabilidad

28

Triángulo de Pascal

1

3

1

4

1

2

6

1

3

1

4

1

1

1

© E. Sucar, PGM: 2 Probabilidad

1

29

Referencias

• [Liu] Capítulo 3
• [Johnsonbaugh] Capítulo 4

© E. Sucar, PGM: 2 Probabilidad

30

Ejercicios

• Cuántos comités diferentes de 3 personas puede

haber a partir de un grupo de 10 individuos?

• De cuántas diferentes maneras pueden repartirse 5

cartas a partir de 52 cartas (pokar)?

• De una urna con 10 bolas, 6 rojas y 4 negras,
cuántas formas diferentes existen al extraer 4
bolas, asumiendo que cada vez que se saca una, se
regresa a la urna?

© E. Sucar, PGM: 2 Probabilidad

31

Ejercicios

• Cuántos comités de 3 estudiantes se pueden

generar en el grupo (40 h, 20 m) si en el comité
debe haber al menos un hombre y una mujer?

• Genera todas la permutaciones para 5 elementos

(en orden lexicográfico)

• Dados 10 problemas, cuántos exámenes diferentes
se pueden generar: (a) no importa el orden de los
problemas, (b) si importa el orden

© E. Sucar, PGM: 2 Probabilidad

32

Ejercicios

• Extiende el algoritmo para generar permutaciones

para r de n elementos

• Un paciente tiene 0, una o dos de 5 posibles
enfermedades; y al menos un síntoma de 10
posibles síntomas. ¿Cuántas posibles
combinaciones de enfermedades-síntomas puede
tener?

• Un robot puede observar de 1 a 3 marcas en un
mapa con 50 marcas en cierto momento, cuántas
posibles combinaciones de marcas puede observar

© E. Sucar, PGM: 2 Probabilidad

33