guia teoria de conteo. alonzo charry
Post on 02-Aug-2015
128 Views
Preview:
TRANSCRIPT
Matemática Discreta Prof. Alonzo Charry
UNIVERSIDAD DR RAFAEL BELLOSO CHACIN
FACULTAD DE INGENIERIA
ESCUELA DE INFORMATICA
CATEDRA: MATEMATICA DISCRETA
UNIDAD II
GUIA: TEORIA DEL CONTEO
PAGINAS: 16
PROF. ALONZO CHARRY
1
Matemática Discreta Prof. Alonzo Charry
UNIDAD II
Teoría del Conteo
Regla de la suma
Si una primera tarea puede realizarse de m formas y una segunda tarea puede realizarse de n formas, y no es posible realizar ambas tareas de manera simultánea, entonces para realizar cualquiera de ellas pueden utilizarse cualquiera de m + n formas.
Ejemplo
Una biblioteca tiene 40 libros de historia y 50 de filosofía. Si un estudiante quiere
aprender acerca de alguno de estos dos temas, por la regla de la suma puede elegir
entre 40 + 50 = 90 libros.
(Nota: el estudiante no quiere estudiar historia y filosofía, sino historia o filosofía.)
La regla puede ampliarse a más de dos tareas, siempre que ningún par de ellas pueda
ocurrir simultáneamente.
Regla del producto
Si un procedimiento se puede descomponer en dos etapas y si existen m
resultados posibles de la primera etapa, y 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 m.n formas.
2
Matemática Discreta Prof. Alonzo Charry
Ejemplos
1. Para una obra de teatro hay 6 hombres y 8 mujeres que aspiran a los papeles
principales. El director puede elegir a la pareja principal de 6.8 = 48 formas.
Esta regla también puede ampliarse a más de dos etapas.
2. Si las placas de los automóviles constan de 2 letras seguidas de 4 dígitos, y
ninguna letra o dígito se puede repetir, ¿cuántas placas diferentes son posibles?
27.26.10.9.8.7 = 3.538.080.
Si se pueden repetir las letras y los dígitos, serán posibles 27.27.10.10.10.10 =
7.290.000 placas diferentes.
Definición
Factorial
Para un natural n, se define n! (n factorial) como:
0! = 1
n! = n(n-1)(n-2)...3.2.1 para n >= 1
Notar que n! = n(n-1)!
Definición
Permutación
Dado un conjunto de n elementos, se denomina permutación a cada uno de los
conjuntos que se pueden formar con estos elementos tales que cada uno de ellos
difiere de otro en el orden en que son considerados los elementos.
Dicho de otro modo, dada una colección de n objetos distintos, cualquier disposición
lineal de estos objetos se denomina permutación de la colección.
3
Matemática Discreta Prof. Alonzo Charry
Pongamos un ejemplo: un grupo de 5 personas va a sentarse en fila para una foto.
¿Cuántas disposiciones lineales son posibles?
5 4 3 2 1
------ ------ ------ ------ ------
1a pos 2a pos 3a pos 4a pos 5a pos
Cualquiera de las 5 personas puede ocupar la primera posición de la fila. Para la
segunda posición podemos elegir entre 4 personas. Continuando de esta manera, sólo
tenemos una persona para ocupar la quinta posición. Esto produce un total de 5.4.3.2.1
= 120 disposiciones posibles de las 5 personas. Se obtiene exactamente la misma
respuesta si las posiciones se ocupan en otro orden (por ejemplo, 3ª posición, 1ª
posición, 4ª, 5ª y 2ª).
En general, si existen n objetos distintos, el número de permutaciones para los n
objetos es
n(n-1)(n-2)...1 = n!
| | | |
| | | n-ésima pos
| | 3ª pos
| 2ª pos
1ª pos
Pn = n!
Se lee "permutaciones de n".
Ejemplo
Dadas las letras a, b, c existen seis formas de disponerlas: P3 = 3! = 3.2.1 = 6.
Las seis permutaciones son:
a b c
a c b
b a c
4
Matemática Discreta Prof. Alonzo Charry
b c a
c a b
c b a
Definición
Arreglos
Dado un conjunto de n elementos, se denomina arreglos de tamaño r a todos los
conjuntos de r elementos escogidos de entre los n, tales que un conjunto difiere de otro
en al menos un elemento o en el orden en que se consideran los elementos.
Consideremos el ejemplo siguiente: en un grupo de 10 personas, se elegirá a 5 y
se les ubicará en fila para una foto. ¿Cuántas disposiciones son posibles?
10 9 8 7 6
------ ------ ------ ------ ------
1a pos 2a pos 3a pos 4a pos 5a pos
Cualquiera de las 10 personas puede ocupar la primera posición de la fila. Para
ocupar la segunda posición tenemos 9 personas. Siguiendo de esta manera, hay 6
personas de donde elegir para que ocupen la quinta posición. Esto produce 10.9.8.7.6
= 10.240 disposiciones posibles.
En general, si existen n objetos distintos, y r es un entero, con 0 <= r <= n,
entonces el número de arreglos de tamaño r para los n objetos es
n!
n(n-1)(n-2)...(n-r+1) = ------
| | | | (n-r)!
| | | r-ésima pos
| | 3ª pos
| 2ª pos
1ª pos
5
Matemática Discreta Prof. Alonzo Charry
n n!
Ar = ------
(n-r)!
Se lee "arreglos de n en r".
Ejemplo
Dadas las letras a, b, c podemos formar 6 arreglos de tamaño 2.
3 3! 3.2.1
A2 = --- = ----- = 6
1! 1
Los 6 arreglos son:
a b
b a
a c
c a
b c
c b
Definición
Combinaciones
Dado un conjunto de n elementos, se denomina combinaciones de tamaño r a
todos los conjuntos que se pueden formar con r elementos tomados de entre los n
elementos, de modo que cada conjunto difiera de los demás en por lo menos un
elemento.
Siguiendo con el mismo ejemplo, si en un grupo de 10 personas se elegirá a 5
para tomarles una foto, ¿cuántos grupos de 5 pueden formarse, si el orden no importa?
6
Matemática Discreta Prof. Alonzo Charry
Si el orden importara, habría A105 disposiciones diferentes. Pero en este caso no
interesa el orden, así que si una de las posibilidades es Juan, María, Luis, Ana y Pedro,
entonces la permutación Luis, Pedro, María, Ana y Juan corresponde a la misma
combinación. Cada grupo de 5 personas puede ordenarse de 5! formas diferentes. Así,
cada combinación corresponde a 5! permutaciones. Por lo tanto, el número de
combinaciones satisface P5.(nº de combinaciones) = A105
o sea que el número de combinaciones es igual a
10
A5
---- = 252
P5
En general, dados n objetos distintos, el número de combinaciones de tamaño r
de estos objetos, con 0 <= r <= n, se denota Cnr y corresponde a
n
n Ar n!
Cr = ---- = --------
Pr r!(n-r)!
Se lee "combinaciones de n en r".
Ejemplo
Dadas las letras a, b, c existen 3 combinaciones de tamaño 2.
3 3!
C2 = ---- = 3
2!1!
Las 3 combinaciones son:
a b
7
Matemática Discreta Prof. Alonzo Charry
a c
b c
Combinaciones complementarias
Demostración:
n n! n! n
Cn-r = ---------------- = -------- = Cr
(n-r)!(n-(n-r))! (n-r)!r!
Ejemplo
Resolver la siguiente ecuación:
10 10
Cx+2 = C3x
Hay dos posibilidades:
que las combinaciones sean idénticas, es decir que x+2 = 3x => 2x = 2 => x = 1.
O que sean combinaciones complementarias, en cuyo caso x + 2 + 3x = 10, o
sea 4x = 8, o sea x = 2.
Teorema de Stieffel
Demostración:
n n n! n! n!(r-1)!(n-r+1)! + n!r!(n-r)!
Cr + Cr-1 = ------- + ------------ = -----------------------------
r!(n-r)! (r-1)!(n-r+1)! r!(n-r)!(r-1)!(n-r+1)!
8
Matemática Discreta Prof. Alonzo Charry
n!(r-1)!(n-r)!(n-r+1+r)! n!(n+1) (n+1)! n+1
= ------------------------ = --------- = --------- = Cr
| r!(n-r)!(r-1)!(n-r+1)! r!(n-r+1) r!(n+1-r)
|
sacamos factores comunes: n!(r-1)!(n-r)!
Ejemplo
Hallar m en la siguiente ecuación:
6 6 7
Cm-1 + Cm-2 = C2
7 7
Cm-1 = C2
=> m - 1 = 2 => m = 3
m - 1 + 2 = 7 => m = 6
Tanto m=3 como m=6 son solución de la ecuación
9
Matemática Discreta Prof. Alonzo Charry
Ejercicios
Recordar que con frecuencia existen varias vías para resolver un problema dado.
Tener en cuenta también que resulta muy útil hacer esquemas o dibujos para visualizar
mejor los problemas.
Reglas de la suma y el producto
1. ¿Cuántas palabras de tres letras se pueden formar con cinco consonantes y tres
vocales de modo que cada palabra comience y termine en consonante?
2. Determine el número de enteros de seis dígitos (que no comiencen con cero) en
los que
3. Ana y María vieron a dos hombres alejarse en automóvil frente a una joyería,
justo antes de que sonara una alarma contra robos. Cuando fueron interrogadas
por la policía, las dos jóvenes dieron la siguiente información acerca de la placa
(que constaba de dos letras seguidas de cuatro dígitos). María estaba segura de
que la segunda letra de la placa era una O o una Q, y que el último dígito era un
3 o un 8. Ana dijo que la primera letra de la placa era una C o una G y que el
primer dígito era definitivamente un 7.
¿Cuántas placas diferentes tendrá que verificar la policía?
4. Tres pueblos, designados como A, B y C, están intercomunicados por un
sistema de carreteras de doble sentido.
a. ¿De cuántas formas puede Juan ir del pueblo A al pueblo C?
b. ¿Cuántos trayectos puede hacer Juan del pueblo A al pueblo C y de
regreso al pueblo A?
c. ¿Cuántos de los trayectos completos de la parte (b) son tales que el viaje
de regreso (del pueblo C al pueblo A) es diferente, al menos
10
Matemática Discreta Prof. Alonzo Charry
parcialmente, de la ruta que toma Juan del pueblo A al pueblo C? (Por
ejemplo, si Juan viaja de A a C por las rutas R1 y R6 podría regresar por
las rutas R6 y R2, pero no por R1 y R6).
Permutaciones
1.
a. ¿Cuántas permutaciones existen para las ocho letras a,b,c,d,e,f,g,h?
b. ¿Cuántas de las permutaciones de (a) comienzan con la letra a?
c. ¿Cuántas de las permutaciones de (a) comienzan con la letra a y
terminan con la letra c?
2. ¿De cuántas formas es posible ordenar los símbolos a,b,c,d,e,e,e,e,e de modo
que ninguna e quede junto a otra?
3.
a. ¿De cuántas maneras se pueden colocar las letras de VISITING?
Si consideramos que las tres I son distintas, podemos formar P8 palabras.
Así, la permutación VI1SI2TI3NG sería distinta de VI2SI1TI3NG. Pero esto
no es lo que queremos, en realidad no hay diferencia entre esas dos
permutaciones. Como las tres I pueden ubicarse de P3 maneras, cada
palabra se está repitiendo P3 veces. Por lo tanto hay P8/P3 = 8!/3! =
6.720 disposiciones diferentes.
b. ¿Cuántas de ellas tienen las tres letras I juntas?
Las restantes 5 letras pueden ordenarse de P5 formas. Las 3 letras I
pueden ubicarse en 6 posiciones diferentes: al principio, al final o en
cualquiera de los 4 espacios entre las otras 5 letras. Así, hay 6.5! = 6! =
720 palabras con las tres I juntas.
11
Matemática Discreta Prof. Alonzo Charry
Combinaciones
1. Un estudiante que realiza un examen debe responder 7 de las 10 preguntas. El
orden no importa. ¿De cuántas formas puede responder el examen?
2. Juan quiere dar una fiesta para algunos de sus amigos. Debido al tamaño de su
casa, sólo puede invitar a 11 de sus 20 amigos. ¿De cuántas formas puede
seleccionar a los invitados?
3. En una reunión de 6 personas, ¿cuántos saludos de mano pueden
intercambiarse, si entre cada 2 personas, se dan la mano una sola vez?
4. Una persona que sale de vacaciones desea llevarse 4 libros para leer: dispone
de 4 novelas policiales y 6 libros de cuentos cortos. ¿De cuántas formas puede
hacer la elección si quiere llevar al menos una novela?
5. ¿Cuántos bytes contienen
a. exactamente dos unos?
b. exactamente cuatro unos?
c. exactamente seis unos?
d. al menos seis unos?
6. ¿De cuántas formas es posible distribuir 12 libros diferentes entre cuatro niños
de modo que
a. cada niño reciba tres libros.
b. los dos niños mayores reciban cuatro libros cada uno y los dos menores
reciban dos libros cada uno.
7. Un comité de 12 personas será elegido entre 10 hombres y 10 mujeres. ¿De
cuántas formas se puede hacer la selección si
a. no hay restricciones?
b. debe haber seis hombres y seis mujeres?
c. debe haber un número par de mujeres?
d. debe haber más mujeres que hombres?
e. debe haber al menos 8 hombres?
12
Matemática Discreta Prof. Alonzo Charry
Arreglos
1. Cuatro nadadores van a disputar la final del campeonato mundial. Los premios
son: 1º-medalla de oro, 2º-medalla de plata y 3º-medalla de bronce. ¿De cuántas
maneras pueden ser distribuidas esas medallas?
2. Con los dígitos 0,1,2,3,4,5
a. ¿Cuántos números de tres cifras se pueden formar?
b. ¿Cuántos son pares?
3.
a. ¿Cuántas palabras pueden formarse con las letras de la palabra
TRIANGULO?
b. ¿Cuántas comienzan con T y terminan en O?
c. ¿Cuántas tienen las 4 vocales juntas?
d. ¿En cuántas la A ocupa lugar impar?
e. ¿En cuántas la A y la O ocupan lugares impares simultáneamente?
13
Matemática Discreta Prof. Alonzo Charry
Principio del palomar
Este interesante principio fue formulado por primera vez de manera formal por
Peter Gustav Lejeune Dirichlet (1805-1859), y en consecuencia se conoce a veces
como el principio de distribución de Dirichlet o el principio de la caja de Dirichlet.
Dirichlet contribuyó mucho en las matemáticas aplicadas y la teoría de números.
Además realizó un trabajo fundamental con respecto a la definición de una función. Su
trabajo enfatizaba la relación entre dos conjuntos de números y no pedía la existencia
de una fórmula o expresión que relacionara los dos conjuntos.
Si m palomas ocupan n nidos y m > n, entonces al menos un nido tiene dos o
más palomas en él.
Ejemplo
Una oficina emplea a 13 oficinistas, por lo que al menos dos de ellos deben
cumplir años durante el mismo mes.
Los 13 oficinistas son las palomas y los 12 meses del año son los nidos. A cada
paloma le corresponde un nido (el mes en que cumple años). Como hay más palomas
que nidos, hay al menos un nido (mes) con dos o más palomas (oficinistas que
cumplen en ese mes).
Ejercicios
1. Demuestre que si 8 personas están en una habitación, al menos dos de ellas
cumplen años el mismo día de la semana.
2. En una lista de 600.000 palabras, donde cada palabra consta de 4 o menos
letras minúsculas, ¿pueden ser las 600.000 palabras distintas?
3. Si una persona puede tener no más de 200.000 cabellos, ¿es posible que en
una ciudad de 300.000 habitantes haya dos personas con la misma cantidad de
cabellos en la cabeza?
14
Matemática Discreta Prof. Alonzo Charry
4. ¿Cuántas veces debemos tirar un sólo dado para obtener el mismo resultado
a. al menos dos veces?
b. al menos tres veces?
c. al menos n veces, para n >= 4?
5. Cualquier subconjunto de tamaño 6 del conjunto A={1,2,3,4,5,6,7,8,9} debe
contener dos elementos cuya suma es 10. Justificarlo.
Los pares de elementos de A que suman 10 son: {1,9}, {2,8}, {3,7} y {4,6}. Estos
son los nidos. Las palomas son los 6 números del subconjunto. Cada número va
al "nido" correspondiente, por ejemplo, el 1 va a {1,9}, el 2 va al {2,8}, y así.
Como 6 > 4, hay al menos dos números que van al mismo nido, es decir, hay
dos números que suman 10. (Si uno de los números es el 5, no lo consideramos,
de todas maneras hay 5 palomas y 4 nidos.)
1 2 8 3 7 4
{1,9}, {2,8}, {3,7} y {4,6}
Aplicación en Algoritmos
15
Matemática Discreta Prof. Alonzo Charry
¿Cuánto vale la variable k después de correr el siguienteprograma (escrito en Python)?k = 0for i in [0,..,19]:
k=k+1k = 0for j in [0,..,29]:
k=k+1
¿Cuánto vale la variable k después de correr el siguienteprograma?k = 0for i in [0,..,19]:
for j in [0,..,29]:k=k+1
¿Cuánto vale la variable n después de correr el siguienteprograma?n = 0for i in [1,..,14]:
for j in [1,..,i]:for k in [1,..,j]:
n=n+1
Bibliografía:
Matemáticas Discretas. Autor: Richard JohnsonBaugh. Editorial Iberoamérica. Capitulo 3. Métodos de conteo
Matemáticas Discretas. Autor: Ramón Espinosa Armenta. Editorial Alfaomega. Capitulo 8. Conteo
http://www2.uca.es/matematicas/Docencia/ESI/1711003/Apuntes/Leccion3.pdf
16
top related