Un3CombinatoriaA

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