Vista previa del material en texto
Unidad 3
Combinatoria
CONTEO
� La enumeración no termina con la aritmética.
� Tiene aplicaciones en áreas como álgebra, la
probabilidad y estadística (matemáticas) y el
análisis de algoritmos (en ciencias de la
computación).
� A medida que vayamos entrando en este
fascinante campo de las matemáticas, nos
encontraremos con muchos problemas que
se pueden enunciar en forma sencilla pero
que son “duros” de resolver.
Conteo
� Las técnicas de conteo son aquellas que
son usadas para enumerar eventos difíciles de cuantificar.
� Ejemplo :
� ¿Cuántas maneras tiene una persona
de seleccionar una lavadora, una batidora y dos
licuadoras, si encuentra en una tienda 8 modelos
diferentes de lavadoras, 5 modelos diferentes de
batidoras y 7 modelos diferentes de licuadoras?.
� Se les denomina técnicas de conteo a las:
� Combinaciones
� permutaciones
� Las bases para entender el uso de las técnicas de conteo
son el principio aditivo y el multiplicativo.
Principio Aditivo
� Si se desea llevar a efecto una actividad, la cuál
tiene formas alternativas para ser realizada, donde:
� la primera de esas alternativas puede ser realizada
de M maneras, la segunda alternativa puede
realizarse de N maneras
� ..... y la última de las alternativas puede ser
realizada de W maneras,
� Entonces esa actividad puede ser llevada a cabo
de :
� M + N + .........+ W maneras
Ejemplo
� La biblioteca de la FCC tiene 40 libros de
texto de programación y 50 de matemáticas.
� Por la regla de la suma, un estudiante de
esta facultad puede elegir entre
40+50=90 libros de texto
� para aprender acerca de alguno de estos dos
temas.
Ejercicio
� Un estudiante puede elegir un proyecto de
computación desde una de tres listas. Las
tres listas contienen 23, 15, y 19 posibles
proyectos, respectivamente. Ningún proyecto
esta en más de una lista. ¿Cuántos posibles
proyectos son posibles de elegir?
Solución
� 23+15+19=57 formas de elegir un proyecto
Ejercicio
� ¿Cuál es el valor de k, dado el siguiente
código?
PRINCIPIO MULTIPLICATIVO
� Si se desea realizar una actividad que consta de r
pasos, en donde el primer paso de la actividad a
realizar puede ser llevado a cabo de N1 maneras,
el segundo paso de N2 maneras y el r-ésimo paso
de Nr maneras, entonces esta actividad puede ser
llevada a efecto de:
� N1 x N2 x ..........x Nr maneras
� El principio multiplicativo implica que cada uno de
los pasos de la actividad deben ser llevados a
efecto, uno tras otro.
PRINCIPIO MULTIPLICATIVO
� Ejemplo : “Una persona desea armar una computadora, para lo
cuál considera que puede seleccionar la Motherboard de entre
las dos disponibles, mientras que el procesador puede ser
seleccionado de un Pentium IV, un Celeron o un Athlon, la
tarjeta de video puede ser una ATI Radeon o una GForce y por
último hay disponible un solo modelo de gabinete (Tower).
� ¿Cuantas maneras tiene esta persona de armar su PC?”
� � Respuesta 2*3*2*1=12
Ejercicio
� Una compañía con dos empleados, Sanchez
y Perez, rentan un piso de un edificio con 12
oficinas. ¿Cuántas formas se pueden usar
para asignar diferentes oficinas a estos dos
empleados?
Solución
� 12*11=132 formas
Ejercicio
� Las sillas de un auditorio son etiquetadas con
una letra del alfabeto seguida por un número
positivo (hasta 100). ¿Cuántas etiquetas
pueden asignarse a una silla?
Solución
� 26*100=2600 formas diferentes
Ejercicio
� Existen 32 computadoras en un centro de
computación. Cada computadora tiene 24
puertos. ¿Cuántos puertos diferentes para
una computadora existen en el centro?
� El procedimiento de elegir un puerto consiste
de dos tareas, primero seleccionamos una
computadora y entonces seleccionamos un
puerto para esa computadora. Debido a que
existen 32 formas de elegir la computadora y
24 formas de elegir un puerto. Por la regla
del producto existen 32*24= 768 puertos.
Ejercicio
� ¿Cuántas cadenas de bits diferentes existen
de longitud siete ?
� Cada uno de los siete bits se puede elegir de
dos formas, porque cada bit es o 0 o 1. Por lo
tanto, por la regla del producto existen en
total 27=128 cadenas diferentes de bits de
longitud siete.
Ejercicio
� ¿Cuántas placas de circulación diferentes
pueden formarse si cada placa contiene una
secuencia de tres letras del alfabeto del
Ingles seguida por tres dígitos (y ninguna
secuencia de letras esta prohibida)?
Solución
� Existen 26 elecciones para cada una de las
tres letras del alfabeto Ingles y 10 elecciones
para cada uno de los tres dígitos. Por lo
tanto, por la regla del producto existen un
total de 26*26*26*10*10*10=17,576,000
posibles placas de circulación.
Contando funciones
� ¿Cuántas funciones existen desde un
conjunto con m elementos a un conjunto con
n elementos?
Solución
� Una función corresponde a elegir de uno de
los n elementos en el codominio para cada
uno de los m elementos en el dominio. Por lo
tanto, por la regla del producto existen
n*n*…*n=nm funciones desde un conjunto
con m elementos a uno con n elementos.
� Por ejemplo, existen 53=125 funciones
diferentes desde un conjunto con tres
elementos a un conjunto con cinco
elementos.
Contando funciones uno-a-uno
� ¿Cuántas funciones uno-a-uno existen desde un conjunto con m
elementos a una con n elementos?
� Primero nota que cuando m>n no existen funciones uno-a-uno
desde un conjunto con m elementos a un conjunto con n
elementos.
� Ahora sea m<=n. Suponga que los elementos en el dominio son
a1, a2, …, am. Existen n formas de elegir el valor de la función
para a1. Como la función es uno a uno, el valor de la función en
a2 puede elegirse de n-1 formas (porque el valor usado para a1
no puede volverse a usar de nuevo).
� En general, el valor de la función en ak se puede elegir de n-k+1
formas. Por la regla del producto, existen n(n-1)(n-2)…(n-m+1)
funciones uno-a-uno desde un conjunto con m elementos a una
con n elementos.
� Por ejemplo, existen 5*4*3=60 funciones uno a uno desde un
conjunto con tres elementos a un conjunto con cinco elementos.
Ejercicio
� ¿Cuál es el valor de k al termino del siguiente
código, donde n1, n2, …,nm son número
positivos?
Solución
� n1*n2*…*nm.
Contando subconjuntos de un conjunto
finito
� Usa la regla del producto para demostrar que el
número de diferentes subconjuntos de un conjunto
finito S es 2|S|.
� Sea S un conjunto finito. Lista los elementos de S
en un orden arbitrario. Existe una correspondencia
uno-a-uno entre los subconjuntos de S y una
cadena de bit’s de longitud |S|. Un subconjunto de S
es asociado con una cadena de bits con un 1 en la
i-esima posición si el i-esimo elemento en la lista
esta en el subconjunto, y un 0 en otro caso. Por la
regla del producto, existen 2|S| cadenas de bits de
longitud |S|. Por lo tanto, |P(S)|=2|S|.
PRINCIPIO ADITIVO Y
MULTIPLICATIVO
� ¿Cómo podemos distinguir cuando hacer uso
del principio multiplicativo y cuando del
aditivo?
� Cuando se trata de una sola actividad la cual
requiere para ser llevada a cabo de una serie
de pasos, entonces haremos uso del
principio multiplicativo y si la actividad a
desarrollar o a ser efectuada tiene
alternativas para ser llevada a cabo,
haremos uso del principio aditivo.
Ejercicio
� En una versión del lenguaje de programación
BASIC, el nombre de una variable es una cadena
de uno o dos caracteres alfanuméricos, donde las
letras mayúsculas y minúsculas no son
distinguibles.
� Un carácter alfanumérico es o uno de los 26 letras
en Ingles o uno de los 10 dígitos.
� Más aún, el nombre de una variable debe iniciar con
una letra y deben ser diferentes de las cinco
cadenas de dos caracteres que están reservadas
para usos de programación. ¿Cuántas nombres de
variable diferentes existen en esta versión de
Basic?
Propuesta de solución - análisis
� En una versión del lenguaje de programaciónBASIC, el nombre de una
variable es una cadena de uno o dos caracteres alfanuméricos, donde
las letras mayúsculas y minúsculas no son distinguibles. V =
v_1 + v_2
� V_1 : variables de longitud 1
� V_2 : variables de longitud 2
� Un carácter alfanumérico es o uno de los 26 letras en Ingles o uno de
los 10 dígitos. (26+10=36)
� V_1 = 26
� V_2 = 26*36
� Más aún, el nombre de una variable debe iniciar con una letra y deben
ser diferentes de las cinco cadenas de dos caracteres que están
reservadas para usos de programación.
� V_2 = 26*36 – 5 =931
� ¿Cuántas nombres de variable diferentes existen en esta versión de
Basic? V= v_1 + v_2 = 26 + 931 = 957
Ejercicio
� Cada usuario de un sistema de computo
tiene un password, el cual es de seis a ocho
caracteres de longitud, donde cada carácter
es una letra o un digito.
� Cada password debe contener al menos un
digito.
� ¿Cuántos posibles passwords existen?
Solución
� P – número de posibles passwords
� P = P_6 + P_7 + P_8
� (longitud 6 + longitud 7 + longitud 8)
� P_6 debe contener al menos un digito
� P_7 debe contener al menos un digito
� P_8 debe contener al menos un digito
Solución
� P – número de posibles passwords
� P = P_6 + P_7 + P_8 = 2,684,483,063,360
� (longitud 6 + longitud 7 + longitud 8)
� Quitamos a cada cadena, las cadenas que sólo tienen letras
� P_6 = 366 – 266 = 2,176,782,336 – 308,915,776 = 1,867,866,560
� P_7 = 367 – 267 = 78,364,164,096 – 8,031,810,176 =
70,332,353,920
� P_8 = 368 – 268 = 2,821,109,907,456 – 208,827,064,576 =
2,612,282,842,880
Regla de substracción (Inclusión-exclusión
para dos conjuntos)
� Si una tarea se realiza de n1 formas o n2
formas, entonces el número de formas para
hacer la tarea es n1 + n2 menos el número
de formar para hacer la tarea que es común
en las dos formas diferentes.
� Principio de Inclusión - exclusión
Ejemplo
� ¿Cuántas cadenas de bits de longitud 8 o
inician con un 1 o terminan con dos bits 00?
128 + 64 – 32 = 160
Ejercicio
� Una compañía de computación recibe 350
aplicaciones de graduados de computación
para un trabajo de servicios Web. Suponga
que 220 de estas aplicaciones están
especializadas en ciencias de la
computación, 147 están especializadas en
negocios, y 51 en ambos. ¿Cuántas de estas
aplicaciones no están especializadas en
ciencias de la computación ni en negocios?
Solución
� |A1 U A2| = |A1| + |A2| - |A1 ∩ A2| = 220 +
147 – 51 = 316
� Conclusión
� 350 – 316 = 34
Diagrama de Árbol
� ¿Cuántas cadenas de bits de longitud 4 no
tienen 2 consecutivos 1’s? 8 cadenas
Diagrama de árbol, ejercicio
� Una eliminatoria entre dos equipos consiste
de a lo más cinco juegos. El primer equipo
que gane los tres juegos gana la eliminatoria.
¿En cuantos formas diferentes puede ocurrir
la eliminatoria?
Diagrama de árbol, ejercicio
� 20 diferentes formas para ganar la
eliminatoria.
Ejercicio
� Suponga que la playera “I love Mexico” viene en
cinco diferentes tamaños: S, M, L, XL, XXL. Más
aún suponga que cada tamaño viene en cuatro
colores, blanco, rojo, verde y negro, excepto para
XL, que sólo viene en verde, rojo y negro, y la XXL,
viene en sólo verde y negro. ¿Cuántas playeras
diferentes debe abastecerse una tienda para que
tenga por lo menos una playera de cada color y
tamaño?
Solución
� 17 playeras
Principio del palomar
� Si k es un entero positivo y k+1 o más
objetos son colocados en k cajas, entonces
existe al menos una caja que contiene dos o
más objetos.
Ejemplo
� Corolario: Una función f desde un conjunto con k+1
o más elementos a un conjunto con k elementos es
uno a uno.
� Dem: Suponga que para cada elemento y en el
codominio de f tenemos una caja que contiene
todos los elementos x del dominio de f tal que
f(x)=y.
� Como el dominio contiene k+1 o más elementos y el
codominio contiene solo k elementes, el principio
del palomar nos dice que una de estas cajas
contiene dos o más elementos x del dominio. Esto
significa que f no puede ser uno a uno.
Ejemplo
� En cualquier grupo de 367 personas, debe
existir al menos dos personas con el mismo
día de cumpleaños, porque existen sólo 366
posibles días de cumpleaños.
� En cualquier grupo de 27 palabras en Ingles,
debe existir al menos dos que inician con la
misma letra, porque hay 26 letras en el
alfabeto del Ingles.
Ejercicio
� ¿Cuántos estudiantes debe tener un curso
para garantizar que al menos dos
estudiantes reciban el mismo puntaje en un
examen final, si el resultado del examen se
encuentra en la escala de 0 a 100 puntos?
Solución
� Existen 101 posibles puntajes en el examen
final. Por el principio del palomar mostramos
que entre 102 estudiantes existen al menos 2
estudiantes con el mismo puntaje.
Generalización del principio del palomar
� Si N objetos son colocados en k cajas,
entonces existe al menos una caja que
contiene al menos objetos.
� Ejemplo
� En un grupo de 100 personas existe al menos
= 9 que nacieron el mismo mes.
k� /
12/100
Ejercicio
� ¿Cuál es el número mínimo de estudiantes
requeridos en la clase de matemáticas
discretas para asegurar que al menos seis
recibirán la misma calificación, si existen
cinco posibles calificaciones, 10, 9 , 8, 7 y 6?
Solución
� El número mínimo de estudiantes necesarios
para asegurar que al menos 6 estudiantes
reciban la misma calificación es el entero N
más pequeño tal que =6. El más
pequeño entero es N= 5*5 +1 = 26.
Entonces, 26 es el número mínimo de
estudiantes necesarios para asegurar que al
menos seis estudiantes reciban la misma
calificación.
5/�
Ejercicio
� Calcular el número total de comidas con dos
platos posibles del siguiente menú:
� Menú Sopa Du Joir
� Crema de la Crema
� Crema de Tomate
� Platos Principales
� Rosbif con Papas o Coles de Bruselas
� Lomo de cerdo con Manzana, Mango, o Papaya
Ejercicio
� Consideremos tres conjuntos
� conjuntos I, II y III.
� I ={a, m, r}
� II = {b, d, i, l,u}
� III = {c, e, n, t}
� Cuántos modos hay para elegir una letra de los
conjuntos I, II y III. Nótese que estos tres conjuntos son
disjuntos o mutuamente excluyentes, es decir no hay elementos
en común entre ellos.
� Usando nuestros tres conjuntos I, II y III. Determinar el número
de conjuntos de tres letras que pueden ser creados tales que
una letra sea de I, una de II y la otra de III.
Ejercicio
� Un matrimonio decide comprar una radio y
una cocina. Si en el lugar donde harán la
compra hay 4 tipos de radio y 2 tipos de
cocina. ¿De cuántas maneras distintas
pueden realizar la compra de ambos objetos
a la vez?
Ejercicio
� Una pareja quiere ir al sur de Chile. Para ir
en avión hay 2 compañías y para ir en
autobús hay 3 compañías. ¿Cuántas
maneras tienen para ir al sur?
Permutaciones
� Muchos problemas de conteo se pueden
resolver encontrando el número de formas
para organizar un número específico de
distintos elementos de un conjunto de cierto
tamaño, donde el orden de estos elementos
importa.
� Otros problemas de conteo se pueden
resolver al encontrar el número de formas
para seleccionar un número particular de
elementos desde un conjunto de cierto
tamaño, donde el orden de los elementos
seleccionados no importa.
Permutaciones, ejemplo
� ¿En cuantas formas podemos seleccionar tres estudiantes de un grupo
de cinco estudiantes colocados en línea para la toma de una
fotografía? ¿De cuantas formas organizamos a los 5 de estos
estudiantes en una línea para la fotografía?
� Primero, notamos que el orden en cual seleccionemos a los estudiantes
importa. Existen 5 formas para seleccionar el primer estudiante colocado al
inicio de la línea. Una ves que este estudiante ha sido seleccionado, hay 4
formas para seleccionar el segundo estudiante colocado en la línea.Después del primero y segundo seleccionados, hay 3 formas para
seleccionar el tercer estudiante para colocarlo en la línea. Por la regla del
producto, hay 5*4*3 =60 formas de seleccionar a tres estudiantes de un
grupo de cinco estudiantes para colocarlos en línea para la toma de la
fotografía.
� Para organizar a los 5 estudiantes en una línea, seleccionamos al primer
estudiante, el segundo en 4 formas, el tercero en 3 formas, el cuarto en 2
formas, y el quinto en una forma. Por lo tanto, hay 5*4*3*2*1=120 formas de
organizar a los 5 estudiantes en una línea para la toma de una fotografía.
Permutaciones
� Una permutación de un conjunto de distintos
objetos es una arreglo ordenado de estos objetos.
� Un arreglo ordenado de r elementos de un conjunto
se llama un r-permutación.
� Ejemplo: Sea S={1,2,3}. El arreglo ordenado 3,1,2
es una permutación de S. El arreglo ordenado 3,2
es una 2-permutación de S.
� El número de r-permutaciones de un conjunto con n
elementos se denota por P(n,r).
Ejemplo
� Sea S={a,b,c}.Las 2-permutaciones de S son
arreglos ordenados a, b; a, c; b,a; b, c; c,a; y c, b.
� Consecuentemente, hay seis 2-permutaciones de
este conjunto con tres elementos . Hay seis 2-
permutaciones de un conjunto con tres elementos.
Existen tres formas para elegir el primer elemento
del arreglo. Hay dos formas para elegir el segundo
elemento del arreglo, porque debe ser diferente
desde el primer elemento. Por lo tanto, por la regla
del producto, tenemos P(3,2)=3*2=6.
Permutaciones
� Si n es un entero positivo y r es un entero
con 1 <= r <= n, entonces hay
P(n,r)=n(n-1)(n-2)…(n-r+1)
r-permutaciones de un conjunto con n
elementos distintos.
� Si n y r son enteros con 0<= r <=n, entonces
� P(n,r) = n! / (n-r)!
Ejercicio
� ¿Cuántas formas existen para seleccionar el
ganador de un primer premio, el ganador de
un segundo premio y el ganador de un tercer
premio de 100 personas diferentes que han
entrado a un concurso?
Solución
� 3-permutaciones de un conjunto de 100
elementos.
� P(100,3)=100*99*98 = 970,200