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
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
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
Regla de la suma
m
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
Regla de la suma
MaestroA
(5)
MaestroB
(3)
|MaestroA  MaestroB| = x
5x8
MaestroA
(5)
MaestroA (5)
MaestroB
(3)
MaestroB
(3)
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
10
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
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
Ejemplo 1
 Permutaciones de “COMPUTER”
 Tomando cuatro letras sin repeticiones
P (8 , 4 ) 
8!
(8  4 )!

8!
 1, 680
4!
 Dos letras sin repeticiones
P (8 , 2 ) 
8!
(8  2 )!
Matemáticas Discretas para el Diseño Geométrico:
Conteo

8!
 56
6!
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  5 )!

66 !
 1, 072 , 431 ,360
61!
Matemáticas Discretas para el Diseño Geométrico:
Conteo
16
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}
2 8
3
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
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 ! n 2 ! n r !
Matemáticas Discretas para el Diseño Geométrico:
Conteo
20
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
Ejemplo
 Disposiciones en MASSASAUGA
 n=10
 t1=“M”, n1=1
 t2=“A”, n2=4
10 !
 t3=“S”, n3=3
(1! )( 4! )( 3! )( 1! )( 1! )
 25 , 200
 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
Disposiciones circulares
 6 rotaciones por cada
disposición.
 Por tanto, si d =
disposiciones circulares
 Ejemplo:
 ABEFCD / BEFCDA /
 EFCDAB / FCDABE /
CDABEF / DABEFC /
6 d  P ( 6 ,6 )
6 d  6!
d 
6!
6
d  5!
d  120
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
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
Combinaciones (sin repetición)
 Selección de n objetos sin tener en cuenta el orden.
C (n, r ) 
P (n, r )
r!
n
 
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 !
3! ( 49 ! )

52  51  50  49 !
6  49 !
52  51  50
Matemáticas Discretas para el Diseño Geométrico:
Conteo
6
 22 ,100
31
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
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.
n=20, r=12
 Hay 20 tipos diferentes.
C ( 20  12  1,12 )
 (Suponemos que hay al

C ( 31 ,12 )
= 141,120, 525
menos una docena de
cada tipo.)
Matemáticas Discretas para el Diseño Geométrico:
Conteo
35
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
n
              2
0 1 2
n
Ejemplo 1
æ 2 ö 0 2 æ 2 ö 1 1 æ 2 ö 2 0
(x + y) = ç
÷x y +ç
÷x y +ç
÷x y
è 1 ø
è 2 ø
è 0 ø
2
(x + y)2 = y 2 + 2xy + x 2
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    21 x y   y
7
5
Matemáticas Discretas para el Diseño Geométrico:
Conteo
2
7
39
Teorema multinomial
 Para (x1 + x2 + x3 +…+ xt)n
n!
n1 ! n 2 ! n 3 !... n n !
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
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
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
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
Descargar

Conteo - Sara E. Garza