Objetivos generales Aplicar algunas de las herramientas que
proveen las matemáticas discretas en la solución de
problemas de electrónica, computación e
información. Aplicar algunas de las herramientas que
proveen las matemáticas discretas en la modelación
formal de situaciones reales relacionadas con el manejo de
información Reconocer la importancia que tiene fundamentar
las soluciones a problemas reales a través de
teorías y modelos formales.
Temario Conjuntos Relaciones y Grafos Arboles y Lenguajes
Semigrupos, grupos y máquinas de estado finito.
Bibliografía Libro de texto Grimaldi, R. P, Discrete and
Combinational Mathematics: An Applied Introduction, 5a
Edición, Pearson Addison Wesley, 2003. QA39.2 G75
1999 y QA39.2 G7518 1998 Rosen, K. H. Matemáticas
discretas y sus aplicaciones, 5a Edición, McGrawHill,
2004. Libros de consulta Johnsonbaugh, R, Matemáticas
Discretas, 4a Edición, Prentice Hall, 1999. QA39.2 J5418
1999 Grossman, Peter. Discrete mathematics for computing. 2a
edición. New York : Palgrave Macmillan, 2002. QA76.5
G78 2002 Haggarty, Rod. Discrete mathematics for computing.
Harlow, England ; New York : Addison-Wesley, 2002 . QA76.9.M35
H34 2002 Anderson, James Andrew. Discrete mathematics with
combinatorics. Upper Saddle River, N.J. : Prentice Hall, 2001.
QA39.2 A53 2001 Scheinerman, Edward R. Matemáticas
discretas. México : Thomson Learning, 2001. QA39.2 S3418
2001 Kolman, B., Busby, R. C. y Ross, S. C. Estructuras de
matemáticas discretas para la computación. 2ª
Edición. México : Prentice-Hall Hispanoamericana ,
1997. QA76.9.M35 K6518 1997
Análisis combinatorio Principios fundamentales del conteo
Permutaciones Combinaciones Teorema binomial Sucesiones y
sumas
1. Principios fundamentales del conteo Regla de la suma. Si una
primer tarea puede realizarse de m formas, mientras una segunda
tarea puede realizarse de n formas, y las dos tareas no pueden
realizarse simultaneamente, entonces la realización de
cualquiera de las tarea se puede llevar a cabo en alguna de las
m+n formas. Módulo 1
La Biblioteca de un colegio tiene 40 libros de texto de
sociología y 50 deantropología. ¿Con
cuántas opciones cuenta un estudiante para realizar
unaconsulta sobre alguno de los dos temas en su Biblioteca? Un
profesor de ciencias de la computación posee 7 libros
introductorios de C++, 7 de Java y 7 de Perl.
¿Cuántas recomendaciones bibliográficas
puede hacera un estudiante interesado en aprender un lenguaje de
programación? Un instructor tiene dos colegas. Uno tiene
tres libros sobre Análisis de algoritmos,y el otro cinco
sobre el mismo tema. ¿Cuál es el número de
libros diferentes quepuede pedir prestados a sus colegas?
Módulo 1 Regla del producto. Si un procedimiento se puede
dividir en dos etapas y existen m posibles resultados para la
primera etapa, y si para cada uno de estos resultados existen n
posibles resultados para la segunda etapa, entonces el
procedimiento total puede llevarse a cabo en el orden
diseñado en m×n formas.
El club de drama de la Universidad Central realiza audiciones
para la obra de primavera. Se presentan 6 hombres y 8 mujeres a
la audición para los papelesprincipales.
¿Cuántas parejas principales diferentes es posible
tener? Las placas de automovil constan de dos letras y cuatro
dígitos. A) ¿Cuántas placas diferentes es
posible tener si ninguna letra o dígito se repite ? B)
¿Y si se permite la repetición de letras y
dígitos? C) Si se permiten las repeticiones
¿Cuántas placas tienen solo vocales y
dígitos par? En la corporación AWL, la Sra. Foster
está a cargo de la cafetería. El menú
estálimitado a seis tipos de panqué, ocho tipos de
sandwich y cinco bebidas diferentes(agua, refresco, café,
té y jugo). La Sra. Dodd, editora de AWL, envía a
su asistente a la cafetería a recoger sualmuerzo: un
panqué con una bebida caliente, o un sandwich con una
bebida fria. ¿Cuántas formas tiene la sra. Dodd de
armar la primera opción de menú, y cuantas para la
segunda opción?
Módulo 1 2. Permutaciones. Dada una colección de n
objetos distintos, cualquier arreglo lineal de estos objetos es
llamado permutación de la colección. Para un entero
n = 0, n factorial (denotado n!) está definido por 0! = 1,
n! = (n)(n-1)(n-2)…(3)(2)(1) para n = 1. Si tenemos n
objetos distintos y r es un número entero, con n = r = 1,
entonces, por la regla del producto, el número de
permutaciones de tamaño r para los n objetos es: P(n,r) =
n! / (n-r)! Donde no se permiten las repeticiones.
En una clase con 10 estudiantes, se han elegido a 5 para tomarles
una foto. ¿Cuántos arreglos diferentes es posible
realizar? ¿Cuántas permutaciones es posible
realizar con la palabra COMPUTER? Y si solo empleamos 5 letras de
la palabra ¿Cuántas tenemos?
Módulo 1 Si se permiten las repeticiones, por la regla del
producto tendremos nr posibles arreglos con r = 1. Nuevamente, de
la palabra COMPUTER, si se permite la repetición de
letrasy queremos formar palabras con 12 letras
¿Cuántos arreglos podemos tener?
¿Cuántos arreglos de 9 letras se pueden formar con
la palabra DATABASESsi las Aes y las eSes no se distinguen? Si
existen n objetos con n1 objetos indistinguibles de un primer
tipo, n2 objetos indistinguibles de un segundo tipo, …, nr
objetos indistinguibles de un r-ésimo tipo donde n1 + n2 +
… + nr = n entonces existen n!/(n1! n2! … nr!)
arreglos lineales de los n objetos dados. ¿Cuántos
arreglos se pueden formar con la palabra MASSASAUGA si las
letrasrepetidas no se distinguen? ¿Cuántas de estas
palabras tienen las 4 Aes juntas?
Determina el número de caminos en el plano x-y para ir del
punto (1, 2) a (7, 4)si solo se permiten movimientos hacia arriba
y a la derecha. Si seis personas se sientan alrededor de una mesa
redonda ¿Cuántos arreglos circulares diferentes es
posible realizar? Consideremos que un arreglo esel mismo que otro
si el primero se obtiene a partir de una rotación del
segundo. Si ahora tenemos tres parejas de casados y queremos
arreglar a la gente alrededorde la mesa de modo que queden
alternados los géneros. ¿Cuántos arreglos
podemos formar? De nuevo consideramos que las rotaciones son
iguales.
Módulo 1 3. Combinaciones. Dada una colección de n
objetos distintos, cada combinación de r de estos objetos,
sin importar el orden, corresponden a r! permutaciones de
tamaño r de los n objetos. De modo que el número de
combinaciones de tamaño r de una colección de
tamaño n es: C(n,r) = P(n,r)/r! = n! / [r!(n-r)!] Donde 0
= r = n. Notemos que:
¿De cuántas maneras se pueden dar tres cartas de
una baraja de 52 que consta de cuatro grupos (figuras) de 13
cartas diferentes? El orden no hace diferencia. Un
anfitrión realiza una fiesta para los miembros del
comité de caridad al quepertenece. Debido a que su casa es
muy pequeña solo puede invitar a 11 de los20 miembros del
comité. ¿De cuantas maneras puede elegir a los 11
invitados? Lina y Paty han comprado un billete de
“melate”. Para ganar el premio mayor deben acertar a
cinco números del 1 al 49, y además a un
número del 1 al 42. ¿De cuántas formas
pueden seleccionar los seis números de su billete?
Un estudiante debe presentar su examen de historia donde debe
responder asiete de 10 preguntas. ¿De cuántas
maneras puede seleccionar sus preguntas? Si el estudiante debe
responder a tres preguntas de las cinco primeras y a cuatro de
las otras cinco. ¿De cuántas maneras puede hacer su
selección? Finalmente, si se le indica que debe responder
a siete preguntas, y al menos a tres de las cinco primeras
¿Cuántas composiciones porsibles tiene? En la
preparatoria, el maestro de deportes debe seleccionar a nueve
niñas de primer y segundo año para formar el equipo
representativo de volleyball. Si hay28 niñas en primer
año y 25 en segundo ¿Cuántos equipos
diferente puede armar? Ahora, si dos niñas de primero y
una de segundo son muy buens jugadoras y debenestar en el equipo.
¿De cuántas maneras puede elegir al resto del
equipo? Finalmente, para cierto torneo las reglas dictan que el
equipo debe consistir de cuatro niñas de primer año
y cinco de segundo ¿Cuántas combinaciones son
posibles? Ahora el maestro de deportes debe formar cuatro equipos
con nueve niñas cada unode 36 estudiantes. ¿De
cuantas maneras puede seleccionar y armar los equipos?
Módulo 1 Combinaciones con repetición. Recordemos:
Cuando se permiten repeticiones, para n objetos distintos, un
arreglo de tamaño r se puede obtener de nr formas si r =
0. En el caso de combinaciones, donde el orden no importa, si
deseamos seleccionar con repetición r de n objetos
distintos el número es:
Una tienda de donas ofrece 20 diferentes tipos de éstas.
Asumiendo que existenal menos una docena de cada tipo cuando
llegamos a la tienda, ¿De cuántas maneras podemos
seleccionar una docena de donas para llevar a casa? De camino a
casa del campo de prácticas, siete chicos paran en la
cafetería donde cada uno puede elegir entre una
hamburguesa, un hotdog, un taco o un emparedado para comer.
¿Cuántas ordenes diferentes se pueden formar? La
presidente Elena tiene cuatro vicepresidentes: Betty, Goldie,
Mary y Mona. Elladesea distribuir $10000, en billetes de $1000,
como bono navideño entre ellas. Considerando que uno o
más vicepresidentes pueden no recibir nada, ¿de
cuántasformas puede dar los billetes? Ahora, si cada
vicepresidente recibe al menos $1000, ¿de cuántas
maneras puededar los bonos? Y si cada vicepresidente recibe al
menos $1000, y Mona al menos $5000, ¿decuántas
maneras puede distribuir el dinero restante?
Módulo 1 Nota: Si el orden es relevante pensamos en
términos de permutación, arreglos y regla del
producto. Si el orden no es relevante, las combinaciones juegan
un papel importante en la solución de problemas.
Módulo 1 4. Teorema binomial. Sean las variables x, y y n
un entero positivo, entonces: Para cada entero n > 0,
En la expansión (x + y)7. ¿Cuál es el
coeficiente de x5y2? En la expansión (2u – 3v)7.
¿Cuál es el coeficiente de u5v2?
Módulo 1 Teorema multinomial. Para los enteros positivos
n,t, los coeficientes en la expansión de cada coeficiente
es Donde cada ni es un entero con 0 = ni = n, para toda 1 = i = t
y n1+ n2+ n3+…+ nt= n.
En la expansión (a + 2b – 3c + 2d + 5)16.
¿Cuál es el coeficiente de a2b3c2d5? En la
expansión (x + y + z)7. ¿Cuál es el
coeficiente de x2y2z3? ¿de xyz5? ¿y de x3z4?
5. Sucesiones y sumas. Una sucesión es una estructura
discreta empleada para representar listas ordenadas. Se suele
emplear la notación {an } para describir a una
sucesión, donde n es un número entero en {1, 2, 3,
…} o {0, 1, 2, 3, …}. La sucesión {an} donde
an = 1/n es {1, ½, 1/3, …} Una progresión
geométrica es una sucesión de la forma a, ar, ar2,
…, arn, donde a y r son números reales. La
sucesión {bn} donde bn = (-1)n para b1, b2, …, es
-1, 1, -1, … La sucesión {cn} donde cn = 2×5n
para c1, c2, …, es 10, 50, 250, … Módulo
1
Módulo 1 Una progresión aritmética es una
sucesión de la forma a, a +d, a + 2d, a + 3d, …, a
+ nd, donde a y r son números reales. La sucesión
{sn} donde sn = -1 + 4n para s0, s1, …, es -1, 3, 7,
… La sucesión {tn} donde tn = 7 – 3n para t0,
t1, …, es 7, 4, 1, -2, … Determina las sucesiones
siguientes: n2 n3 2n 3n n! Determina la fórmula de las
sucesiones siguientes: a)1, ½, ¼, 1/8, … b)
1, 3, 5, 7, 9, …
Módulo 1 Sumatoria. Una manera concisa de escribir la suma
de una sucesión de n+1 términos es empleando la
notación de sumatoria: Donde i es el índice de la
suma y contabiliza a todos los enteros a partir del límite
inferior m hasta el límite superior m+n.
Ejemplos de sumatorias: