20/05/2014

Capítulo 1 Grimaldi

Contenidos  Introducción  Reglas  de la suma  del producto  Permutación  sin repeticiones  con repeticiones  elementos repetidos  circular

 Combinación  sin repeticiones  con repeticiones  Coeficiente  binomial  Multinomial  Ejercicios

Matemáticas Discretas para el Diseño Geométrico: Conteo

2

1

20/05/2014

Introducción  Incertidumbre  información masiva nos rebasa  varias opciones juntas causan una “explosión” de posibilidades  Ocupamos métodos que nos ayuden a saber de “cuánto estamos hablando”.

Matemáticas Discretas para el Diseño Geométrico: Conteo

3

Conteo  Combinatoria  Enunciar la cantidad de      

opciones, posibilidades, maneras, patrones, objetos con ciertas características, etc.

Matemáticas Discretas para el Diseño Geométrico: Conteo

4

2

20/05/2014

Conteo  Aplicaciones en  Teoría de códigos  Probabilidad y estadística  Análisis de algoritmos

Matemáticas Discretas para el Diseño Geométrico: Conteo

5

Conceptos básicos de conteo

Matemáticas Discretas para el Diseño Geométrico: Conteo

6

3

20/05/2014

m

Regla de la suma

n

 Si una primera tarea puede realizarse de m formas,  mientras que una segunda tarea puede realizarse de n formas,  y no es posible realizar ambas tareas de manera simultánea,  entonces, para llevar a cabo cualquiera de ellas  pueden utilizarse cualquiera de m + n formas. Matemáticas Discretas para el Diseño Geométrico: Conteo

7

Regla de la suma Antropología (50)

Sociología (40)

|Sociología| + |Antropología|= 40 + 50= 90

4

20/05/2014

Regla de la suma MaestroA (5)

MaestroB (3)

MaestroA (5)

|MaestroA  MaestroB| = x 5x8

m

MaestroB (3)

MaestroA (5) MaestroB (3)

n

Regla del producto  Si un procedimiento se puede descomponer en las etapas primera y segunda,  y si existen m resultados posibles de la primera etapa  y, si para cada uno de estos resultados,  existen n resultados posibles para la segunda etapa,  entonces el procedimiento total se puede realizar, en el orden dado, de mn formas. Principio de elección Matemáticas Discretas para el Diseño Geométrico: Conteo

10

5

20/05/2014

Ejemplo 1

Matemáticas Discretas para el Diseño Geométrico: Conteo

11

Ejemplo 2  Principio de elección

Comité A

Comité B

a

1

b

2

3

6

20/05/2014

El orden importa.

Matemáticas Discretas para el Diseño Geométrico: Conteo

13

Permutación  Disposición lineal de objetos, dada una colección con n de éstos.

P(n, r ) 

Matemáticas Discretas para el Diseño Geométrico: Conteo

n! (n  r )!

14

7

20/05/2014

Ejemplo 1  Permutaciones de “COMPUTER”  Tomando cuatro letras sin repeticiones

P(8,4) 

8! 8!   1,680 (8  4)! 4!

 Dos letras sin repeticiones

P(8,2) 

8! 8!   56 (8  2)! 6!

Matemáticas Discretas para el Diseño Geométrico: Conteo

15

Ejemplo 2  Considerando {a…z, A…Z, 0-9, #,$,+,*}  ¿Cuántas contraseñas de 5 caracteres son posibles si no se repite ningún caracter?

P(66,5) 

66! 66!   1,072,431,360 (66  5)! 61!

Matemáticas Discretas para el Diseño Geométrico: Conteo

16

8

20/05/2014

Permutación con repeticiones

n

r

 Permutaciones de “COMPUTER”  Tomando cuatro letras  84=4,096  Tomando dos letras  82=64

Matemáticas Discretas para el Diseño Geométrico: Conteo

17

Otro ejemplo  Cadenas de 3 letras con {a,b}

23  8 Maneras de escoger la primer letra

2 2 2  8 Maneras de escoger la tercer letra Maneras de escoger la segunda letra Matemáticas Discretas para el Diseño Geométrico: Conteo

18

9

20/05/2014

Matemáticas Discretas para el Diseño Geométrico: Conteo

19

Disposiciones con elementos repetidos  Existen  n1 objetos (indistinguibles) de un primer tipo,  n2 objetos de un segundo tipo,… y  nr objetos de un r-ésimo tipo, 

Ej. “BALL”, “PEPPER”

n! n1!n2! nr ! Matemáticas Discretas para el Diseño Geométrico: Conteo

20

10

20/05/2014

Ejemplo  Disposiciones en BALL  n=4  t1=“B”, n1=1  t2=“A”, n2=1  t3=“L”, n3=2

4!  12 (1!)(1!)(2!)

Matemáticas Discretas para el Diseño Geométrico: Conteo

22

Ejemplo  Disposiciones en PEPPER  n=6  t1=“P”, n1=3  t2=“E”, n2=2  t3=“R”, n3=1

6!  60 (3!)(2!)(1!)

Matemáticas Discretas para el Diseño Geométrico: Conteo

23

11

20/05/2014

Ejemplo  Disposiciones en MASSASAUGA  n=10

 t1=“M”, n1=1

10!  25,200 (1!)(4!)(3!)(1!)(1!)

 t2=“A”, n2=4  t3=“S”, n3=3  t4=“U”, n4=1  t5=“G”, n5=1

Matemáticas Discretas para el Diseño Geométrico: Conteo

24

Disposiciones circulares  Si seis personas, designadas como A, B, …,F se sientan en torno de una mesa redonda, ¿cuántas disposiciones circulares diferentes son posibles, si las disposiciones se consideran iguales cuando una puede obtenerse de otra mediante una rotación?  Ejemplo: ABEFCD = BEFCDA

Matemáticas Discretas para el Diseño Geométrico: Conteo

25

12

20/05/2014

Disposiciones circulares  6 rotaciones por cada disposición.  Ejemplo:  ABEFCD / BEFCDA /  EFCDAB / FCDABE / CDABEF / DABEFC /

 Por tanto, si d = disposiciones circulares

6d  P(6,6) 6d  6!

6! 6 d  5! d  120 d

Matemáticas Discretas para el Diseño Geométrico: Conteo

26

Disposiciones circulares  Otra manera de resolver el problema:  Dejar “A” fijo  Calcular las disposiciones lineales de B…F (=5!)

Matemáticas Discretas para el Diseño Geométrico: Conteo

27

13

20/05/2014

Disposiciones circulares  Supongamos ahora que las personas deben sentarse alternando sexos (hombre-mujer).  Igual, se deja “A” fijo (mujer 1)  3 maneras de escoger cómo se sentará el hombre 1  2 “ ” la mujer 2  2 “ ” el hombre 2  1 “ ” la mujer 3 3  2  2 11  12  1 “ ” el hombre 3 Matemáticas Discretas para el Diseño Geométrico: Conteo

28

Selecciones. No importa el orden.

Matemáticas Discretas para el Diseño Geométrico: Conteo

29

14

20/05/2014

Combinaciones (sin repetición)  Selección de n objetos sin tener en cuenta el orden.

C (n, r ) 

P(n, r ) n!  r! r!(n  r )!

n   r

“Combinaciones de n en r”, “Combinaciones de n tomando r” Matemáticas Discretas para el Diseño Geométrico: Conteo

30

Ejemplo 1  Obtener 3 cartas de una baraja normal  A, J, R = A, R, J = R, J, A = J, R, A = J, A, R = R, A, J  52  52! 52!      3  3!(52  3)! 3!(49!)

52! 52  51 50  49!  3!(49!) 6  49!

52  51 50  22,100 Matemáticas Discretas para el Diseño Geométrico: 6 Conteo

31

15

20/05/2014

Ejemplo 2  Ejemplo: Tienes 4 amigos y escoges 2 para llevar al baile.  C(4,2) = 6  {a1, a2} / {a1, a3} / {a1, a4} / {a2, a3} / {a2, a4} / {a3, a4}

Matemáticas Discretas para el Diseño Geométrico: Conteo

32

Equivalencia  C(n, r) = C(n, n-r)  Ejercicio: Demuestra esta equivalencia.

Matemáticas Discretas para el Diseño Geométrico: Conteo

33

16

20/05/2014

Combinaciones con repetición (n  r  1)! r!(n  1)!

 n  r  1   r   Matemáticas Discretas para el Diseño Geométrico: Conteo

34

Ejemplo 1  Escoger una docena de donas.  Hay 20 tipos diferentes.

n=20, r=12

C (20  12  1,12)  C (31,12)

 (Suponemos que hay al

= 141,120, 525

menos una docena de cada tipo.)

Matemáticas Discretas para el Diseño Geométrico: Conteo

35

17

20/05/2014

Teorema del binomio  Coeficiente binomial  Para (x + y)n  Se desea saber el coeficiente de los diferentes términos.  Ejemplo:  (x + y)2 = c1x2y0 + c2x1y1 + c3x0y2  = c1x2 + c2xy + c3y2  c1 = ? / c2 = ? / c3 = ? Matemáticas Discretas para el Diseño Geométrico: Conteo

36

Teorema del binomio æ n ö k n-k (x + y) = åç ÷x y k=0 è k ø n

n

 n n n  n               2n  0 1  2  n

18

20/05/2014

Ejemplo 1 æ ö æ ö æ ö (x + y)2 = ç 2 ÷ x0 y2 + ç 2 ÷ x1 y1 + ç 2 ÷ x2 y0 è 1 ø è 2 ø è 0 ø

(x+ y)2 = y2 + 2xy + x2

Matemáticas Discretas para el Diseño Geométrico: Conteo

38

Ejemplo 2  Calcular el coeficiente de x5y2 en (x + y)7

æ 7 ö æ 7 ö ç ÷=ç ÷ = 21 è 5 ø è 2 ø

x 7    21x5 y 2   y 7

Matemáticas Discretas para el Diseño Geométrico: Conteo

39

19

20/05/2014

Teorema multinomial  Para (x1 + x2 + x3 +…+ xt)n

n! n1!n2 !n3!...nn !

Ejemplos  Para (x + y + z)7, calcular el coeficiente de  x2y2z3 æ 7 çç è 2, 2, 3

ö 7! 7! ÷÷ = = = 210 2!2!3! 4! ø

æ 7 çç è 3, 0, 4

ö 7! 210 ÷÷ = = = 35 3!0!4! 6 ø

 x3y0z4

Matemáticas Discretas para el Diseño Geométrico: Conteo

41

20

20/05/2014

Matemáticas Discretas para el Diseño Geométrico: Conteo

42

Ejercicio  Proporciona ejemplos de los conceptos vistos .  Nivel 1 = Ejemplo didáctico (5 puntos)  Nivel 2 = Ejemplo didáctico en ciencias computacionales

(10 puntos)  Nivel 3 = Ejemplo relacionado con un problema teórico o

con un caso práctico actual (20 puntos)

Matemáticas Discretas para el Diseño Geométrico: Conteo

43

21

20/05/2014

Puede ser en equipo.

Ejercicio  Se espera al menos un ejercicio por tema:  Reglas de suma y producto  Permutaciones  Combinaciones  Calificación máxima: 200

Matemáticas Discretas para el Diseño Geométrico: Conteo

44

Ejercicio  Algunas opciones para investigar  Optimización combinatoria  Física de partículas (checar Cap. 1 Grimaldi)  Teoría de grafos  Autómatas celulares  Problemas NP-completos  Criptografía

Matemáticas Discretas para el Diseño Geométrico: Conteo

46

22

20/05/2014

Matemáticas Discretas para el Diseño Geométrico: Conteo

47

Referencias  Grimaldi, Ralph P (2003). Matemáticas Discreta y

Combinatoria: Una Introducción con Aplicaciones. México: Addison Wesley Longman. 3a. Edición.

Matemáticas Discretas para el Diseño Geométrico: Conteo

48

23