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 n personas – De n personas que fuman, observar cuántas tienen 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 lexicográfico

• Repetir 2 hasta alcanzar la secuencia “mayor” (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 1 1 1 1

1 2

3 4

1 3

6

© E. Sucar, PGM: 2 Probabilidad

1 4

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