APUNTES ADICIONALES_1_COMBINATORIA

Vista previa del material en texto

LIC. GLADYS MONICA ROMANO – MATEMATICA DISCRETA – UTN- FRT Página 1 
 
 
APUNTES ADICIONALES DE 
MATEMATICA DISCRETA 
 
 
 
TEMA 1: Métodos de Conteo y 
Combinatoria 
Contar los elementos de un conjunto en el caso de conjuntos finitos pequeños puede resultar una 
tarea sencilla y bastante obvia. En el caso de conjuntos finitos grandes suele resultar una tarea 
confusa que puede llevarnos a resultados erróneos 
 
Conjuntos finitos pequeños 
Ejemplos : 
Si A = {resultados del lanzamiento de un dado } = { 1 , 2 , 3 , 4 , 5 , 6 } , entonces |A| = 6 
Si B = {resultados del lanzamiento de dos monedas } = { CC , CS , SC , SS} , |B| = 4 
Si C = { resultados del lanzamiento de tres monedas } = {CCC, CCS,CSC,CSS,SCC,SCS,SSC,SSS} , |C| = 8 
 
 
Diagramas de árbol: Un diagrama que ayuda a pensar en el caso de los conjuntos finitos pequeños !! 
Ejemplo: Se lanzan tres monedas, ¿Cuántos resultados son posibles? 
 
 
 
LANZAMIENTO 
DE TRES 
MONEDAS 
C 
C 
C 
S 
S 
C 
S 
S 
C 
C 
S 
S 
C 
S 
{ CCC , CCS , CSC , CSS , SCC , SCS , SSC , SSS } 
LIC. GLADYS MONICA ROMANO – MATEMATICA DISCRETA – UTN- FRT Página 2 
 
Conjuntos finitos grandes 
 
En otros casos tendremos conjuntos finitos tan grandes que es imposible escribirlos a todos 
para poder contarlos. Los Principios de Conteo brindan herramientas para contar los 
elementos de un conjunto por mas grande que éste sea. 
La enumeración de los elementos de un conjunto tiene aplicaciones en áreas como la Teoría 
de Códigos, Análisis de Algoritmos , Probabilidad y Estadística, etc. 
 
1. PRINCIPIOS DE CONTEO 
Una buena técnica para analizar problemas complejos es descomponerlo en etapas que 
puedan resolverse fácilmente, luego aplicar uno o ambos principios que a continuación 
enunciamos: la REGLA DEL PRODUCTO y la REGLA DE LA SUMA 
 
1.1. Regla del Producto 
Si una tarea puede descomponerse en dos etapas, E1 y E2, y si E1 puede realizarse de n1 
maneras y E2 puede realizarse de n2 maneras, entonces la tarea completa puede realizarse 
de n1 . n2 maneras 
 
 
 
 
 
 
Generalización de la Regla del Producto 
Si una tarea puede descomponerse en k etapas, E1 , E2 E3 ...y Ek y si E1 puede realizarse 
de n1 maneras , E2 puede realizarse de n2 maneras, ….y Ek puede realizarse de nk 
maneras entonces la tarea completa puede realizarse de n1 . n2 … nk maneras 
 
 
 
 
LIC. GLADYS MONICA ROMANO – MATEMATICA DISCRETA – UTN- FRT Página 3 
 
EJERCICIOS : 
1) Se lanzan dos dados. ¿Cuántos resultados son posibles? 
2) Se lanza un dado y se tira una moneda. ¿Cuántos resultados son posibles? 
3) ¿Cuántas cadenas de ocho bits hay? (Un bit es un 0 o bien un 1) 
4) Mostrar que un conjunto A = {x1,x2,…,xn} que contiene n elementos , contiene 2
n 
subconjuntos 
Respuesta del 4) Tarea: Formar subconjuntos con los n elementos de A 
Etapas: E1: decidir elegir o no x1 , n1= 2 , E2: decidir elegir o no x2 , n2= 2 
En: decidir elegir o no xn , nn= 2 
Entonces el número posible de subconjuntos es 2.2….2 = 2n 
 
1.2. Regla de la Suma 
Suponga una actividad que puede realizarse mediante cualquiera de dos procedimientos 
excluyentes. Si el primer procedimiento puede realizarse de n1 formas y el segundo 
procedimiento de n2 formas, entonces la actividad puede realizarse por cualquier 
procedimiento de n1 + n2 maneras 
 
 
 
Esta es una consecuencia del Principio de Adición para el caso de conjuntos disjuntos que 
recordemos es |AB = A + B , donde A representaría las formas de hacer la actividad por el 
procedimiento 1 y B representaría las formas de hacer la actividad por el procedimiento 2. 
 
 
 
Generalización de la Regla de la Suma 
Suponga una actividad que puede realizarse mediante cualquiera de k procedimientos 
excluyentes. 
Si el primer procedimiento puede realizarse de n1 formas , el segundo procedimiento de n2 
formas, …y el k-èsimo procedimiento puede hacer de nk formas, entonces la actividad puede 
realizarse por cualquier procedimiento de n1 + n2 +…+ nk maneras 
 
 
 
 
 PROCEDIMIENTO 1 
n1formas 
PROCEDIMIENTO 2 
n2 formas 
La actividad se pueden realizar de n1 + n2 
formas 
LIC. GLADYS MONICA ROMANO – MATEMATICA DISCRETA – UTN- FRT Página 4 
 
EJERCICIOS 
 
1) Un estudiante debe elegir un libro de su biblioteca para leer en las vacaciones. Su 
biblioteca contiene 10 libros distintos de ficción y 14 novelas distintas. ¿De cuántas maneras 
puede hacer la elección? 
2) Se tira un dado dos veces y se registra el resultado de la suma de ambas tiradas. ¿En 
cuántos resultados la suma es 7 o es 11? 
 
Respuesta del 2) Tarea: lanzar el dado dos veces y ver que la suma registra 7 o 11. Hay dos 
procedimientos: Que el resultado sea 7 o que el resultado sea 11. Los resultados forman dos 
conjuntos disjuntos. 
1º procedimiento: Formar 7  n1 = 6 (Ellos son: 1 y 6, 2 y 5 , 3 y 4 , 4 y 3 , 5 y 2 , 6 y 1) 
2º procedimiento: Formar 11  n2 = 2 (Ellos son: 5 y 6 , 6 y 5) 
La suma es 7 o es 11 en 6 + 2 = 8 resultados posibles 
 
2. Combinatoria Simple 
La Combinatoria es la rama de las Matemáticas que estudia la cantidad de maneras de 
realizar agrupaciones con los elementos de un conjunto. Dichas agrupaciones pueden ser 
lineales o circulares, con elementos repetidos o no, sin importar el orden o con interés de 
orden. 
Se llama Combinatoria Simple a aquella parte de la combinatoria que considera 
agrupaciones donde no se pueden repetir elementos 
 
2.1. Permutaciones simples 
Suponga que se quiere crear claves bancarias alfabéticas con la condición de que sean tres 
letras distintas. Un clave posible es AXW pero también WXA ya que si intercambiamos el 
orden se forma otra clave. 
Cada uno de las claves que se pueden formar recibe el nombre de PERMUTACION de 
tamaño 3 del conjunto de las 26 del abecedario. 
Por la regla del producto, deducimos que la cantidad de claves formadas por tres letras 
distintas es : 26*25*24= 15600 
Ahora veremos la fórmula para calcular la cantidad de variaciones de un tamaño r a partir 
de un conjunto de n elementos distintos. 
 
 
 
LIC. GLADYS MONICA ROMANO – MATEMATICA DISCRETA – UTN- FRT Página 5 
 
Cálculo Permutaciones simples 
Teorema: En general, si existen n objetos distintos y r es un natural tal que r n, entonces, 
por la regla del producto, la cantidad de Permutaciones de tamaño r para los n objetos es 
 
Si r = n , se simboliza y se dice que es la cantidad de Permutaciones de n objetos 
 
EJERCICIOS 
1) Calcular la cantidad de permutaciones de dos letras distintas tomadas a partir de las 
letras del conjunto {a,b,c} y escribir cuales son. 
2) Calcular la cantidad de permutaciones de dos letras distintas formadas por las letras 
del conjunto {a,b} y escribir cuales son. 
3) Se desea elegir 5 personas de un grupo de 10 personas para posar en fila para una 
foto. ¿Cuántas disposiciones lineales son posibles? 
4) ¿ Cuál es el número de permutaciones de las letras de la palabra COMPUTER? 
Respuesta a 1) La cantidad de permutaciones de 2 elementos elegidas de un conjunto de 3 
elementos es P3,2 = 3 . 2 = 6 
Ellas son: ab , ac , ba , bc , ca , cb 
Caso especial: Disposiciones circulares 
Cuando se acomodan objetos distintos en forma circular, aquellas disposiciones que se 
consideran solo rotaciones de otra, se consideran iguales. 
Sean los objetos A , B y C tres personas sentadas alrededor de una mesa circular. Observe 
que las siguientes tres disposiciones , leídas en el mismo sentido (horario) , son iguales: 
 
Una disposición distinta a ellas será, por ejemplo: BAC, dejamos fija la letra C del primer 
arreglo y permutamos A y B. Ésta disposición tiene, a su vez, 2 disposiciones iguales a ella, 
leídas todas en el mismosentido. 
 
LIC. GLADYS MONICA ROMANO – MATEMATICA DISCRETA – UTN- FRT Página 6 
 
 
 
Entonces de las 3! disposiciones lineales que se podrían armar hay que calcular cuántos grupos 
de 3 disposiciones iguales se pueden formar. 
El cálculo es: 
 
En general, si se tienen n objetos distintos la cantidad de disposiciones circulares posibles está 
dada por 
 
EJERCICIO 
Si cuatro matrimonios , se sientan en torno de una mesa redonda a cenar , de cuantas 
formas pueden hacerlo, si: 
a) no hay restricciones? 
b) si cada hombre desea estar entre dos mujeres? 
 
Respuesta : 
a) Son ocho personas en un círculo, entonces hay maneras 7! 
b) si cada hombre desea estar entre dos mujeres? 
 E1: se elige lugares para los hombres 
 E2: se elige lugares para las mujeres , intercaladas entre los hombres 
 Entonces pueden sentarse de 3! . 3! = 36 maneras 
 
 
LIC. GLADYS MONICA ROMANO – MATEMATICA DISCRETA – UTN- FRT Página 7 
 
2.2. Combinaciones simples 
Suponga el conjunto de personas {Luis, Ale, Sol} y se desea seleccionar a dos de ellas. Al 
seleccionar personas, entre las cuales no hay jerarquía, nos damos cuenta de que el orden no 
es importante. 
Cada selección de elementos, sin importar el orden, se llama Combinación. En este caso hay 3 
combinaciones posibles 
 
 
Cantidad de Combinaciones simples 
Teorema: En general, si existen n objetos distintos y r es un natural tal que r n, entonces, el 
número de combinaciones de tamaño r para una colección de n objetos es 
 
 
 se lee número combinatorio n sobre r 
Ejercicios 
1) Calcular el número de manos distintas, de cinco cartas, que se pueden dar 
tomándolas de una baraja de 52 cartas si: 
a) No hay restricciones 
b) En la mano de cinco cartas debe haber exactamente 2 cartas de corazones 
c) En la mano de cinco cartas debe al menos 2 cartas de corazones 
Agrupaciones 
de dos 
personas 
tomadas de 
un conjunto 
de tres 
considerando 
el orden 
Luis 
Ale 
Sol 
Ale 
Luis 
Sol 
Sol 
Luis 
Ale 
Descartando aquellas donde 
solo hay una variación del 
orden, quedan 
{ {Luis, Ale} , {Luis, Sol} , {Ale, Sol}} 
{ {Luis, Ale} , {Luis, Sol} ,{Ale, Luis},{Ale, Sol} , 
{Sol, Luis} ,{ Sol, Ale} } 
LIC. GLADYS MONICA ROMANO – MATEMATICA DISCRETA – UTN- FRT Página 8 
 
d) Debe haber cuatro cartas de la misma denominación (con el mismo número 
o letra) 
2) Considerando los arreglos de ocho bits, 
a) Cuantos arreglos de ocho bits contienen exactamente tres ceros? 
b) Cuantos arreglos contienen exactamente tres ceros y todos seguidos? 
c) Cuantos arreglos contienen tres o más ceros seguidos y el resto unos ? 
Respuesta a 1) 
a) Hay manos de cinco cartas distintas 
b) Si debe haber exactamente 2 cartas de corazones . 
c) Si debe haber al menos 2 cartas de corazones . . 
 . = 
d) Para calcular cuantas manos de 5 cartas puedo extraer de tal modo que 4 de esas 
cartas sean de la misma denominación (ejemplo: JJJJ3), descompongo en las 
siguientes etapas: 
E1: Elijo la denominación -> 
E2: Elijo cuatro cartas de la denominación elegida -> 
E3 : Elijo la quinta carta del resto de las cartas -> 
Entonces la cantidad de manos de cartas de tal modo que haya 4 de la misma 
denominación es 
Relación entre P(n,k) y C(n,k) 
Observe que: 
Ejemplo: