Matemática Discreta 1Matemática Discreta 1
Curso 2007Curso 2007
Prof. Eduardo A. CanaleProf. Eduardo A. [email protected]@fing.edu.uy
[email protected]@fing.edu.uy
Información útilInformación útil
Web: Web: http://imerl.fing.edu.uy/matdisc1/http://imerl.fing.edu.uy/matdisc1/ Web antigua: Web antigua:
www.fing.edu.uy/~webimerl/discreta1/principal.htwww.fing.edu.uy/~webimerl/discreta1/principal.htmm
Bibliografía: Bibliografía: Matemáticas Discreta y Combinatoria Matemáticas Discreta y Combinatoria
de R. P. de R. P. GrimaldiGrimaldi..
Elementos de Matemáticas discretasElementos de Matemáticas discretas de de C. L. Liu. C. L. Liu.
[email protected]@fing.edu.uy
TeóricoTeórico
Lunes 13:30 a 15:00 Salón A01 Lunes 13:30 a 15:00 Salón A01 Jueves de 13:00 a 14:30 Salón A11Jueves de 13:00 a 14:30 Salón A11
Coordinador del curso : Coordinador del curso :
Nancy Guelman Nancy Guelman [email protected]@fing.edu.uy.
[email protected]@fing.edu.uy
PrácticosPrácticos
Iguales a los de la año pasado (WEB)Iguales a los de la año pasado (WEB) Prácticos:Prácticos: G4G4 Mi y Vi 17:00 a 18:30 Salón 103 con Mi y Vi 17:00 a 18:30 Salón 103 con
Sebastián SensaleSebastián Sensale G5G5 Mi y Vi 17:00 a 18:30 Salón 014 y 401 con Mi y Vi 17:00 a 18:30 Salón 014 y 401 con
Andrés CorezAndrés Corez G6G6 Mi y Vi 15:30 a 17:00 103 y 101 con Mi y Vi 15:30 a 17:00 103 y 101 con
Sebastián SensaleSebastián Sensale
[email protected]@fing.edu.uy
Temas del cursoTemas del curso
CombinatoriaCombinatoria Relaciones Relaciones GrafosGrafos
[email protected]@fing.edu.uy
Aprobación del cursoAprobación del curso
Combinatoria, (1Combinatoria, (1erer Parcial) 40 ptos Parcial) 40 ptos RelacionesRelaciones GrafosGrafos
Exoneración: 60 puntosExoneración: 60 puntos
2do parcial 60 ptos
[email protected]@fing.edu.uy
CombinatoriaCombinatoria
Técnicas básicas de conteoTécnicas básicas de conteo Inducción completaInducción completa Principio de Inclusión-exclusiónPrincipio de Inclusión-exclusión Principio del palomarPrincipio del palomar Relaciones de recurrenciaRelaciones de recurrencia Funciones generatrices Funciones generatrices
[email protected]@fing.edu.uy
CombinatoriaCombinatoria
Técnicas básicas de conteo Técnicas básicas de conteo (Grimaldi Cap 1)(Grimaldi Cap 1) Reglas de la suma y el producto (Reglas de la suma y el producto (1.11.1)) Arreglos con y sin repeticiónArreglos con y sin repetición ((1.21.2)) Permutaciones con y sin repetición (Permutaciones con y sin repetición (1.21.2)) Combinaciones sin repetición (Combinaciones sin repetición (1.31.3)) Teorema del binomio (Teorema del binomio (1.31.3)) Combinaciones con repetición (Combinaciones con repetición (1.41.4))
[email protected]@fing.edu.uy
CombinatoriaCombinatoria
¿Qué es la combinatoria? ¿Qué es la combinatoria?
¿Qué problemas trata de resolver?¿Qué problemas trata de resolver?
¿Para qué sirve?¿Para qué sirve?
¿Cuándo surgió?¿Cuándo surgió?
[email protected]@fing.edu.uy
CombinatoriaCombinatoria
¿Qué es la combinatoria? ¿Qué es la combinatoria?
Del lat. Del lat. combinārecombināre = com binare = com binare
Com = unirCom = unir
Binare= dos cosas.Binare= dos cosas.
Unir dos o más cosas para formar un Unir dos o más cosas para formar un nuevo objeto.nuevo objeto.
[email protected]@fing.edu.uy
CombinatoriaCombinatoria
Combinación de objetos:Combinación de objetos: ¿Se puede?¿Se puede? ¿Cómo?¿Cómo? ¿Cuánto?¿Cuánto? PropiedadesPropiedades
[email protected]@fing.edu.uy
CombinatoriaCombinatoria
Combinación de objetos:Combinación de objetos: ¿Se puede? ¿Se puede? Existencia Existencia ¿Cómo? ¿Cómo? Algoritmos Algoritmos ¿Cuánto? ¿Cuánto? Conteo Conteo Propiedades: Estudio cualitativo (Grafos)Propiedades: Estudio cualitativo (Grafos)
[email protected]@fing.edu.uy
Técnicas básicas de conteoTécnicas básicas de conteo
Regla del productoRegla del producto::
Si para formar los objetos en el Si para formar los objetos en el 11er er paso tenemospaso tenemos mm posibles posibles salidas y en el segundo salidas y en el segundo nn posibles salidas independientes posibles salidas independientes del paso anterior el total de del paso anterior el total de objetos formados será objetos formados será mm nn
[email protected]@fing.edu.uy
Técnicas básicas de conteoTécnicas básicas de conteo
Regla del productoRegla del producto Arreglos con repetición ARArreglos con repetición ARmm
n n = m= mnn
Arreglos sin repetición AArreglos sin repetición Ammn n = = m(m-1)…(m-m(m-1)…(m-
n+1)n+1) Permutaciones (sin repetición): APermutaciones (sin repetición): Amm
mm = m! = m!
Arreglos con repeticiónArreglos con repetición
[email protected]@fing.edu.uy
Libros de matemáticaLibros de matemática
http://bibliotecabochini.netfirms.com/http://bibliotecabochini.netfirms.com/informacion.htminformacion.htm
[email protected]@fing.edu.uy
Permutaciones con Permutaciones con repeticiónrepetición
Ejemplo:Ejemplo:1.1. aab, aba, baaaab, aba, baa
Son 3 en lugar de 3! = 6.Son 3 en lugar de 3! = 6.
2.2. aabc, aacb, abac, abca, acab, acba, aabc, aacb, abac, abca, acab, acba, baac, baca, bcaa,baac, baca, bcaa,caab, caba, cbaacaab, caba, cbaa
Son 12 en lugar de 4! = 24.Son 12 en lugar de 4! = 24.
[email protected]@fing.edu.uy
Permutaciones con Permutaciones con repeticiónrepetición
Regla general: Regla general: la cantidad de permutaciones la cantidad de permutaciones de una palabra de una palabra aaaabbbbcccc…aaaabbbbcccc… es igual a es igual a
Donde Donde nn11, n, n22, n, n33… es la cantida de … es la cantida de aa’s, ’s, bb’s, ’s, cc’s, etc’s, etc
Obviamnete Obviamnete nn1 1 + + nn2 2 + + nn3 3 + … + … nnkk = = nn..
!!...!
!
21 knnn
n
[email protected]@fing.edu.uy
Permutaciones con Permutaciones con repeticiónrepetición
Ejemplo: Tableros de ta-te-tiEjemplo: Tableros de ta-te-ti
[email protected]@fing.edu.uy
Permutaciones con Permutaciones con repeticiónrepetición
Ejemplo: Tableros de ta-te-tiEjemplo: Tableros de ta-te-ti
[email protected]@fing.edu.uy
Permutaciones con Permutaciones con repeticiónrepetición
¿Cuántos tableros de ta-te-ti hay?¿Cuántos tableros de ta-te-ti hay?
aab
c c
cc c c
aab
c c
cc c
aab
c
c
c cb b
a
[email protected]@fing.edu.uy
Permutaciones con Permutaciones con repeticiónrepetición
¿Cuántos tableros de ta-te-ti hay?¿Cuántos tableros de ta-te-ti hay?
a
ab
c c
c
c c c
a
ab
c c
c
c c
a
ab
c
c
c cb b
a
acccbaccc acccbabcc acacbabcc
[email protected]@fing.edu.uy
Permutaciones con Permutaciones con repeticiónrepetición
¿Cuántos tableros de ta-te-ti hay?¿Cuántos tableros de ta-te-ti hay?
acccbaccc acccbabcc acacbabcc
9!/(2!1!6!)=9x8x7/2=252
9!/(2!2!5!)=9x8x7x6/4= 756
9!/(3!2!4!)=9x8x7x6x5/12=1260
[email protected]@fing.edu.uy
Permutaciones con Permutaciones con repeticiónrepetición
El total se obtiene sumando los El total se obtiene sumando los totales parciales. totales parciales.
Hemos aplicado la Hemos aplicado la Regla de la sumaRegla de la suma que dice así: que dice así: si los objetos que quiero si los objetos que quiero contar los puedo dividir en dos ( o contar los puedo dividir en dos ( o más) tipos distinto, basta contar más) tipos distinto, basta contar cuantos de cada tipo hay y sumar los cuantos de cada tipo hay y sumar los resultados.resultados.
[email protected]@fing.edu.uy
¿Estamos contando de más?¿Estamos contando de más?
¿Son iguales?¿Son iguales?
[email protected]@fing.edu.uy
SimetríasSimetrías
Suele dar lugar a problemas difícilesSuele dar lugar a problemas difíciles Teoría de Redfield y PolyaTeoría de Redfield y Polya: ver por : ver por
ejemplo Grimaldi 16.9 a 16.11 ejemplo Grimaldi 16.9 a 16.11 involucra involucra teoría de gruposteoría de grupos (Discreta (Discreta 2) y 2) y funciones generatricesfunciones generatrices
Casos sencillos: permutaciones Casos sencillos: permutaciones circulares, combinacionescirculares, combinaciones
[email protected]@fing.edu.uy
Permutaciones circularesPermutaciones circulares
Ejemplo: tengo cuatro personas a, b, c y dEjemplo: tengo cuatro personas a, b, c y d ¿Cuántas formas hay de ubicarlas en una ¿Cuántas formas hay de ubicarlas en una
mesa circular?mesa circular? Sea “Sea “xx” dicha cantidad” dicha cantidad
a
b
c
d a
d
c
b
a
b
c
d
[email protected]@fing.edu.uy
Permutaciones circularesPermutaciones circulares
Paso 1 : elijo una de las Paso 1 : elijo una de las x x permutaciones circulares permutaciones circulares Paso 2: la giro de 4 formas posiblesPaso 2: la giro de 4 formas posibles Obtengo: todas las Obtengo: todas las 4!4! Permutaciones Permutaciones (regla del producto(regla del producto) ) xx4=P=4!4=P=4! xx = 4!/4 = 3!= 4!/4 = 3!
a
b
c
d = a
b
c
d
=
a
b
c
d
[email protected]@fing.edu.uy
Permutaciones circularesPermutaciones circulares
En general si tengo n símbolosEn general si tengo n símbolos Hay n giros posibles Hay n giros posibles x x n = n! n = n! De donde De donde xx = = n!/n n!/n = = ((n-1n-1)!)! ¡Qué formula más sencilla!¡Qué formula más sencilla! ¿Habrá otra forma de pensarla ¿Habrá otra forma de pensarla
directamente que de ese resultado?directamente que de ese resultado?
[email protected]@fing.edu.uy
Permutaciones circularesPermutaciones circulares
Otra forma de pensarloOtra forma de pensarlo Fijo a arriba y permuto las otras Fijo a arriba y permuto las otras ((nn-1)-1)
a
b
c
d
a
b
d
c …
a
c
b d
[email protected]@fing.edu.uy
SimetríasSimetrías
La combinatoria involucra: La combinatoria involucra: ObjetosObjetos: generalmente cantidad finita : generalmente cantidad finita
de tiposde tipos Forma de combinarlosForma de combinarlos: geometría : geometría
(lineal, circular, cuadrada, etc)(lineal, circular, cuadrada, etc) SimetríaSimetría: asociada (a la geometría) o : asociada (a la geometría) o ad ad
hoc.hoc.
[email protected]@fing.edu.uy
CombinacionesCombinaciones (sin repetición) (sin repetición)
Otra simetría sencilla: Otra simetría sencilla: toda permutacióntoda permutación da da lugar a objetos equivalentes = “lugar a objetos equivalentes = “no importa no importa el ordenel orden””
Ejemplo: Arreglos de 4 en 3.Ejemplo: Arreglos de 4 en 3. Objetos: a, b, c, dObjetos: a, b, c, d acd =acd = adc =adc = dac = etcdac = etc ¿Cuántos tenemos?¿Cuántos tenemos? 3! = 6: acd = adc = cad = cda = dac = dca3! = 6: acd = adc = cad = cda = dac = dca
[email protected]@fing.edu.uy
CombinacionesCombinaciones
Permutando las combinaciones Permutando las combinaciones obtenemos los arreglos, por lo tanto obtenemos los arreglos, por lo tanto (regla del producto)(regla del producto)
CCnnmm n n!! = = AAnn
mm
CCnnmm= = AAnn
mm/ n/ n! =! =
mm!!
((mm--nn)! )! nn!!
[email protected]@fing.edu.uy
Combinaciones con Combinaciones con repeticiónrepetición
Ejemplo: ¿De cuántas formas puedo Ejemplo: ¿De cuántas formas puedo pedir una media docena de pedir una media docena de biscochos?biscochos?
Supongamos cuatro tipos: a, b, c, dSupongamos cuatro tipos: a, b, c, d ¿Importa el orden? ¿Importa el orden? Ejemplos: aaabbb, aabbcc, etcEjemplos: aaabbb, aabbcc, etc
[email protected]@fing.edu.uy
Combinaciones con Combinaciones con repeticiónrepetición
aaabbb aaabbb = 3 a y 3 b, 0 c, 0 d= 3 a y 3 b, 0 c, 0 d aabbcc = 2 a, 2 b y 2 c, 0 daabbcc = 2 a, 2 b y 2 c, 0 d 3 a y 3 b = a xxx, b xxx, c 0, d, 03 a y 3 b = a xxx, b xxx, c 0, d, 0 2 a, 2 b y 2 c = a xx, b xx, c xx, d 02 a, 2 b y 2 c = a xx, b xx, c xx, d 0 aaabbb = xxx|xxx||aaabbb = xxx|xxx|| aabbcc = xx|xx|xx|aabbcc = xx|xx|xx| ¿abbcdd?¿abbcdd? x|xx|x|xxx|xx|x|xx
[email protected]@fing.edu.uy
Combinaciones con Combinaciones con repeticiónrepetición
aaabbb = xxx|xxx||aaabbb = xxx|xxx|| aabbcc = xx|xx|xx|aabbcc = xx|xx|xx| abbcdd =x|xx|x|xxabbcdd =x|xx|x|xx 11eroero) siempre hay 6 “x” y 3 “|”) siempre hay 6 “x” y 3 “|” 22dodo ) cualquier permutación de 6x y 3 ) cualquier permutación de 6x y 3
| da lugar a una elección distinta| da lugar a una elección distinta ¿Cuántas hay? ¿Cuántas hay?
[email protected]@fing.edu.uy
Combinaciones con Combinaciones con repeticiónrepetición
¿Cuántas hay? Permutaciones con ¿Cuántas hay? Permutaciones con repetición de 6+3 letras con 6 y repetición de 6+3 letras con 6 y 3repetidas = 3repetidas = (6+3)!/(6!3!) = C(6+3)!/(6!3!) = C99
33
En general para En general para CRCRmmnn son son nn “x” y “x” y m-1m-1
“|”“|” Total:Total:
n!(m-1)!= Cn
n+m-1(n+m-1)!
[email protected]@fing.edu.uy
ResumenResumen
RepeticiónRepetición
OrdenOrdenSISI NONO
SISI ARARmmnn AAmm
nn
NONO CRCRmmnn CCmm
nn
[email protected]@fing.edu.uy
ResumenResumen
RepeticiónRepetición
OrdenOrdenSISI NONO
SISI ARARmmn n = m= mnn AAmm
n n ==
NONO CRCRmmnn = C = Cm+n-1m+n-1
nn CCmmnn = =
!)!(
!
nnm
m
!)!(
!
nnm
m
[email protected]@fing.edu.uy
Otra forma de ver las cosasOtra forma de ver las cosas
Combinaciones con repetición de 4 Combinaciones con repetición de 4 en 6en 6
aaabbb = xxx|xxx|| = aaabbb = xxx|xxx|| = 3+3+0+03+3+0+0 Distribución de objetos en cajas: Distribución de objetos en cajas:
objetos y cajas distinguibles o no.objetos y cajas distinguibles o no. Pueden haber cajas vacías o no.Pueden haber cajas vacías o no.
[email protected]@fing.edu.uy
Distribución de objetos en Distribución de objetos en cajascajas
Objetos Objetos
DistiguiblesDistiguibles
Cajas Cajas DistinguiblesDistinguibles
SISI NONO
SISI ? (fácil)? (fácil) CRCRmmnn
NONO ?(no tanto)?(no tanto) ?(difícil)?(difícil)
[email protected]@fing.edu.uy
Otra forma de ver las cosasOtra forma de ver las cosas
Fórmula del Binomio:Fórmula del Binomio:
Por esta razón a los coeficientes CPor esta razón a los coeficientes Cnnii también se los también se los
llama coeficientes binomiales. Se los suele llama coeficientes binomiales. Se los suele denotar de la siguiente formadenotar de la siguiente forma
n
i
inini
n baCba0
)(
i
n
[email protected]@fing.edu.uy
Fórmula del BinomioFórmula del Binomio
Demostración combinatoriaDemostración combinatoria (a+b)(a+b)22 = (a+b) (a+b)= = (a+b) (a+b)= (a(a11+b+b11) (a) (a22+b+b22) =) = (a(a11+b+b11) a) a22+ (a+ (a11+b+b11) b) b22== aa1 1 aa2 2 +b+b11 a a22+ a+ a11bb2 2 +b+b11bb22
(a+b)(a+b)33 = (a = (a11+b+b11) (a) (a22+b+b22) (a) (a33+b+b33)=)= (a(a1 1 aa2 2 +b+b11 a a22+ a+ a11bb2 2 +b+b11bb22) (a) (a33+b+b33)=)= aa1 1 aa22aa3 3 +b+b11 a a22aa33+ a+ a11bb22aa3 3 +…+… + a+ a11bb22bb3 3 + b+ b11bb22bb33
[email protected]@fing.edu.uy
Fórmula del BinomioFórmula del Binomio
Demostración combinatoriaDemostración combinatoria aa1 1 aa22aa3 3 +b+b11 a a22aa33+ a+ a11bb22aa3 3 +…+… + a+ a11bb22bb3 3 + b+ b11bb22bb33
Vemos que por cada término comienza con una Vemos que por cada término comienza con una aa11 o una b o una b1 1 sigue con asigue con a22 o b o b2 2 y termina con ay termina con a33 o b o b33. . Entonces podemos pensar que los términos se Entonces podemos pensar que los términos se construyen en un proceso de tres pasos: construyen en un proceso de tres pasos:
Paso 1 Elijo una de las letras del 1Paso 1 Elijo una de las letras del 1erer factor (a factor (a11+b+b11)) Paso 2 Elijo una de las letras del 2Paso 2 Elijo una de las letras del 2dodo factor (a factor (a22+b+b22)) Paso 3 Elijo una de las letras del 3Paso 3 Elijo una de las letras del 3erer factor (a factor (a33+b+b33))
[email protected]@fing.edu.uy
Fórmula del BinomioFórmula del Binomio
Por otro lado los términos finales se obtiene al borrar Por otro lado los términos finales se obtiene al borrar los índices y juntar los términos iguales. En el los índices y juntar los términos iguales. En el ejemplo:ejemplo:
aaaaaa +baa+ aba+baa+ aba +…+… + abb+ abb + bbb = a+ bbb = a33+3a+3a22b+3abb+3ab22+b+b33
¿De donde sale el “3” de “a¿De donde sale el “3” de “a22b” ?b” ? De juntar aab+aba+baa, es decir de elegir en dos De juntar aab+aba+baa, es decir de elegir en dos
pasos “a” y en el otro “b”.pasos “a” y en el otro “b”. ¿De cuantas formas se pueden elegir 2 “a”?¿De cuantas formas se pueden elegir 2 “a”? Tengo 3 factores, debo elegir 2 de donde elegir Tengo 3 factores, debo elegir 2 de donde elegir
dichas “a”, como no importa el orden en que elija dichas “a”, como no importa el orden en que elija dichos dos factores, tengo Cdichos dos factores, tengo C33
22 formas de hacerlo. formas de hacerlo.
[email protected]@fing.edu.uy
Fórmula del BinomioFórmula del Binomio
En general (a+b)En general (a+b)nn = = ii a aiibbn-in-i Donde Donde ii será todas las formas de será todas las formas de
elegir en i pasos la letra “a”, es decir elegir en i pasos la letra “a”, es decir elegir i factores de entre n: Celegir i factores de entre n: Cnn
ii. .
[email protected]@fing.edu.uy
Algunas ConsecuenciasAlgunas Consecuencias
Ejemplo 1: (1+x)Ejemplo 1: (1+x)nn = = CCnnii 11iixxn-in-i= = CCnn
ii xxn-in-i
=(x+1)=(x+1)nn = = CCnnii xxii11n-in-i= = CCnn
ii xxii
Por lo tanto: CPor lo tanto: Cnnii = C = Cnn
n-in-i
Ejemplo 2: Ejemplo 2:
0= (-1+1)0= (-1+1)nn = = CCnnii (-1)(-1)ii11n-in-i= = CCnn
ii (-1)(-1)ii
Ejemplo 3: Ejemplo 3: 2 2n n = (1+1)= (1+1)nn = = CCnn
ii (1)(1)ii11n-in-i= = CCnn
ii
Este ejemplo además nos da una cota Este ejemplo además nos da una cota (grosera) de los coeficientes binomiales.(grosera) de los coeficientes binomiales.