1 Conteo Capítulo 1 Grimaldi
2 Contenidos Introducción Reglas Permutación Combinación Coeficientede 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
3 Introducción Incertidumbreinformació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
4 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
5 Conteo Aplicaciones en Teoría de códigos Probabilidad y estadísticaAnálisis de algoritmos Matemáticas Discretas para el Diseño Geométrico: Conteo
6 Reglas Conceptos básicos de conteoMatemáticas Discretas para el Diseño Geométrico: Conteo
7 Regla de la suma 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
8 |Sociología| + |Antropología|=Regla de la suma Sociología (40) Antropología (50) |Sociología| + |Antropología|= = 90
9 |MaestroA MaestroB| = xRegla de la suma MaestroA (5) MaestroB (3) MaestroA (5) MaestroB (3) MaestroA (5) |MaestroA MaestroB| = x 5 x 8 MaestroB (3)
10 m 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
11 Ejemplo 1 Matemáticas Discretas para el Diseño Geométrico: Conteo
12 Ejemplo 2 Principio de elección a b Comité A 1 Comité B 2 3
13 Permutaciones El orden importa.Matemáticas Discretas para el Diseño Geométrico: Conteo
14 Permutación Disposición lineal de objetos, dada una colección con n de éstos. Matemáticas Discretas para el Diseño Geométrico: Conteo
15 Ejemplo 1 Permutaciones de “COMPUTER” Dos letras sin repeticionesTomando cuatro letras sin repeticiones Dos letras sin repeticiones Matemáticas Discretas para el Diseño Geométrico: Conteo
16 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? Matemáticas Discretas para el Diseño Geométrico: Conteo
17 Permutación con repeticionesPermutaciones de “COMPUTER” Tomando cuatro letras 84=4,096 Tomando dos letras 82=64 Matemáticas Discretas para el Diseño Geométrico: Conteo
18 Otro ejemplo Cadenas de 3 letras con {a,b}Maneras de escoger la primer letra Maneras de escoger la tercer letra Maneras de escoger la segunda letra Matemáticas Discretas para el Diseño Geométrico: Conteo
19 ¿Cuántos colores son posibles utilizando representación hexadecimal?utilizando el esquema RGB? ¿Cuántos son posibles utilizando representación hexadecimal? Matemáticas Discretas para el Diseño Geométrico: Conteo
20 Disposiciones con elementos repetidosExisten n1 objetos (indistinguibles) de un primer tipo, n2 objetos de un segundo tipo,… y nr objetos de un r-ésimo tipo, Ej. “BALL”, “PEPPER” Matemáticas Discretas para el Diseño Geométrico: Conteo
21 Ejemplos Disposiciones en BALL Disposiciones en PEPPERMatemáticas Discretas para el Diseño Geométrico: Conteo
22 Ejemplo Disposiciones en BALL n=4 t1=“B”, n1=1 t2=“A”, n2=1t3=“L”, n3=2 Matemáticas Discretas para el Diseño Geométrico: Conteo
23 Ejemplo Disposiciones en PEPPER n=6 t1=“P”, n1=3 t2=“E”, n2=2t3=“R”, n3=1 Matemáticas Discretas para el Diseño Geométrico: Conteo
24 Ejemplo Disposiciones en MASSASAUGA n=10 t1=“M”, n1=1 t2=“A”, n2=4t3=“S”, n3=3 t4=“U”, n4=1 t5=“G”, n5=1 Matemáticas Discretas para el Diseño Geométrico: Conteo
25 Disposiciones circularesSi 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
26 Disposiciones circulares6 rotaciones por cada disposición. Ejemplo: ABEFCD / BEFCDA / EFCDAB / FCDABE / CDABEF / DABEFC / Por tanto, si d = disposiciones circulares Matemáticas Discretas para el Diseño Geométrico: Conteo
27 Disposiciones circularesOtra 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
28 Disposiciones circularesSupongamos 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 1 “ ” el hombre 3 Matemáticas Discretas para el Diseño Geométrico: Conteo
29 Selecciones. No importa el orden.Combinaciones Selecciones. No importa el orden. Matemáticas Discretas para el Diseño Geométrico: Conteo
30 Combinaciones (sin repetición)Selección de n objetos sin tener en cuenta el orden. “Combinaciones de n en r”, “Combinaciones de n tomando r” Matemáticas Discretas para el Diseño Geométrico: Conteo
31 Ejemplo 1 Obtener 3 cartas de una baraja normalA, J, R = A, R, J = R, J, A = J, R, A = J, A, R = R, A, J Matemáticas Discretas para el Diseño Geométrico: Conteo
32 Ejemplo 2 Ejemplo: Tienes 4 amigos y escoges 2 para llevar al baile.{a1, a2} / {a1, a3} / {a1, a4} / {a2, a3} / {a2, a4} / {a3, a4} Matemáticas Discretas para el Diseño Geométrico: Conteo
33 Equivalencia C(n, r) = C(n, n-r)Ejercicio: Demuestra esta equivalencia. Matemáticas Discretas para el Diseño Geométrico: Conteo
34 Combinaciones con repeticiónMatemáticas Discretas para el Diseño Geométrico: Conteo
35 Ejemplo 1 Escoger una docena de donas. n=20, r=12Hay 20 tipos diferentes. (Suponemos que hay al menos una docena de cada tipo.) n=20, r=12 Matemáticas Discretas para el Diseño Geométrico: Conteo
36 Teorema del binomio Coeficiente binomial Para (x + y)n Ejemplo: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
37 Teorema del binomio Corolario
38 Ejemplo 1 Matemáticas Discretas para el Diseño Geométrico: Conteo
39 Ejemplo 2 Calcular el coeficiente de x5y2 en (x + y)7Matemáticas Discretas para el Diseño Geométrico: Conteo
40 Teorema multinomial Para (x1 + x2 + x3 +…+ xt)n
41 Ejemplos Para (x + y + z)7, calcular el coeficiente de x2y2z3 x3y0z4Matemáticas Discretas para el Diseño Geométrico: Conteo
42 Practiquemos Matemáticas Discretas para el Diseño Geométrico: Conteo
43 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
44 Ejercicio Se espera al menos un ejercicio por tema: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
45 Ejercicio Se espera al menos un ejercicio por tema: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 Puntos extra: ¿de cuántas maneras puedes resolver este ejercicio para obtener una calificación mayor o igual a 80? Matemáticas Discretas para el Diseño Geométrico: Conteo
46 Ejercicio Algunas opciones para investigar Optimización combinatoriaFí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
47 Resumen Matemáticas Discretas para el Diseño Geométrico: Conteo
48 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