Upload
others
View
7
Download
0
Embed Size (px)
Citation preview
Unidad 3
Combinaciones
Combinaciones
Contar una selección no ordenada de
objetos.
Ejemplo
¿Cuántos comités diferentes de tres
estudiantes se pueden formar desde un
grupo de cuatro estudiantes? R= 4
{1,2,3}, {1,2,4},{2,3,4}, {3,4,1},
Combinaciones
Una r-combinación de elementos de un conjunto es una selección no ordenada de r elementos del conjunto.
Una r-combinación es un subconjunto con r elementos.
El número de r-combinaciones de un conjunto con n elementos distintos se denota por C(n,r).
También se denota por y se llama Coeficiente binomial
r
n
Teorema
El número de r-combinaciones de un conjunto con n
elementos, donde n es un entero no negativo y r es un entero
con 0<=r<=n,
Las r-permutaciones P(n,r) de un conjunto se obtiene al
formar las r-combinaciones C(n,r) del conjunto, y entonces
ordenamos los elementos en cada r-combinación, la cual se
hace en P(r,r) formas. Por lo tanto, por la regla del producto:
Por lo tanto:
Ejemplo
¿Cuántas manos de póquer de cinco cartas
pueden repartirse de una baraja de 52
cartas? Además, ¿cuántas maneras hay para
seleccionar 47 cartas de una baraja de 52
cartas?
Debido a que el orden en el cual las cinco
cartas se reparten de una baraja de 52 cartas
no importa, existen
C(52,5)= 26*17*10*49*12 = 2,598,960
Hay 2,598,960 diferentes manos de poker
de 5 cartas que pueden ser repartidas de una
baraja de 52 cartas.
Además, C(52,47)=52!/47!*5! Diferentes
formas de seleccionar 47 cartas desde una
baraja de 52 cartas.
C(52,47)=C(52,5)
Corolario
Sea n y r un entero no negativo con r<=n. Entonces C(n,r)=C(n,n-r)
Prueba:
Y
Por lo tanto, C(n,r)=C(n,n-r)
Ejemplo
¿Cuántas formas hay para seleccionar a
cinco jugadores de un equipo de tenis de 10
miembros, para hacer un viaje a un partido
en otra escuela?
La respuesta esta dada por el número de 5-
combinaciones de un conjunto con 10
elementos. Por el teorema anterior, el
número de tales combinaciones es:
Ejercicio
Un grupo de 30 personas han sido
entrenados como astronautas para ir en la
primera misión a Marte. ¿Cuántas maneras
hay para seleccionar una tripulación de seis
personas para ir en esta misión (suponiendo
que todos los miembros de la tripulación
tienen el mismo trabajo)?
Solución Un grupo de 30 personas han sido entrenadas como
astronautas para ir en la primera misión a Marte. ¿Cuántas
maneras hay para seleccionar una tripulación de seis
personas para ir en esta misión (suponiendo que todos los
miembros de la tripulación tienen el mismo trabajo)?
El número de formas para seleccionar una tribulación de 6
desde las 30 personas es el número de 6-combinaciones de
un conjunto con 30 elementos, porque el orden en el cual
estas personas son elegidas no importa. El número de
combinaciones es:
C(30,6)= 30!/6!24! = 30*29*28*27*26*25/6*5*4*3*2*1 =
593,775
Ejemplo
¿Cuántas cadenas de bits de longitud n
contiene exactamente r 1’s?
La posición de r 1’s en una cadena de bits de
longitud n forman una r-combinación del
conjunto {1,2,3,…,n}. Existe C(n,r) de
cadenas de bits de longitud n que contiene
exactamente r 1’s.
Ejercicio
Suponga que hay 9 miembros de la facultad
de matemáticas y 11 de la facultad de
computación. ¿Cuántas formas existen para
seleccionar un comité para desarrollar un
curso de matemáticas discretas en una
escuela, si los comités consisten de tres
miembros de la facultad de matemáticas y
cuatro de la facultad de computación?
Ejercicio Suponga que hay 9 miembros de la facultad de
matemáticas y 11 de la facultad de computación.
¿Cuántas formas existen para seleccionar un
comité para desarrollar un curso de matemáticas
discretas en una escuela, si los comités consisten
de tres miembros de la facultad de matemáticas y
cuatro de la facultad de computación?
Por la regla del producto, el número de formas para
seleccionar el comité es
Teorema binomial
Sea x y y variables, y sea n un entero no
negativo. Entonces
Ejemplo:
Aplica el teorema binomial a:
(x+y)4
Aplica el teorema binomial a:
(x+y)4
Ejercicio
¿Cuál es el coeficiente de x12y13 en la
expansión de (x+y)25?
Ejercicio
¿Cuál es el coeficiente de x12y13 en la
expansión de (x+y)25?
Desde el teorema binomial, el coeficiente es:
Corolario
Sea n un entero no negativo. Entonces, si
Corolario 2
Sea n un entero positivo. Entonces:
Con x=-1 y y=1,
´Corolario
Sea n un entero no negativo. Entonces
Reconocemos que el lado izquierdo de la
fórmula es la expansión de (1+2)n
proporcionado por el teorema binomial.
Por lo tanto,
Identidad y Triángulo de Pascal
Identidad de Pascal, sea n y k enteros
positivos con n>=k. Entonces
Triangulo de Pascal, coeficientes binomiales
Identidad Vandermonde
Sea m, n y r enteros no negativos con r no
excediendo m o n. Entonces
Corolario. Si n es un entero no negativo,
entonces
Teorema
Sea n y r enteros no negativos con r <= n.
Entonces
Permutaciones y Combinaciones
Generalizadas
Los elementos pueden usarse más de una
ves.
Permutaciones con repetición
Ejemplo
¿Cuántas cadenas de longitud r se forman con el
alfabeto de letras mayúsculas en ingles?
Por la regla del producto, como hay 26 letras en ingles,
y porque cada letra se puede usar repetidamente, por lo
que hay 26r cadenas de letras mayúsculas en Ingles de
longitud r.
Teorema
El número de r-permutaciones de un
conjunto con repetición es nr.
Ejercicio
¿De cuántas formas diferentes se pueden
seleccionar 5 elementos en orden desde un
conjunto con 3 elementos cuando la
repetición se permite?
Solución
3*3*3*3*3 = 243
Ejercicio
¿Cuántas cadenas de 6 letras existen?
(considerando 26 letras)
Solución
266 cadenas
Ejercicio
¿Cuántas formas existen para asignar tres
empleos a 5 empleados si cada empleado
puede hacer más de un trabajo?
Solución
5*5*5=125
Combinaciones con repetición Ejemplo
¿Cuántas formas existen para seleccionar cuatro piezas de
fruta de un tazón que contiene manzanas, naranjas y peras;
si el orden en el cual las piezas seleccionadas no importa,
sólo el tipo de fruta y las piezas individuales no importan, y
existen al menos cuatro piezas de cada tipo de fruta en el
tazón?
Solución: Para solucionar este problema se listan las formas
posibles de seleccionar la fruta. Hay 15 formas:
4 manzanas 4 naranjas 4 peras
3 manzanas, 1 naranja 3 manzanas, 1 pera 3 naranjas, 1 manzana
3 naranjas, 1 pera 3 peras, 1 manzana 3 peras, 1 naranja
2 manzanas, 2 naranjas 2 manzanas, 2 peras 2 naranjas, 2 peras
2 manazas, 1 naranja, 1
pera
2 naranjas, 1 manzana, 1
pera
2 peras, 1 manzana, 1
naranja
Ejemplo
¿Cuántas formas hay para seleccionar 5
billetes de una caja que contienen billetes de
$1, $2, $5, $10, $20, $50 y $100? Asume
que el orden en el cual los billetes son
elegidos no importa, que los billetes de cada
denominación son indistinguibles, y que hay
al menos 5 billetes de cada tipo.
Contar 5-combinaciones con repetición
desde un conjunto con 7 elementos.
Solución Supóngase que la caja tiene 7 compartimientos, cada uno para almacenar cada
tipo de billete:
Estos compartimientos son separados por 6 divisiones. La elección de 5 billetes corresponde a colocar 5 marcas en los compartimientos manteniendo diferentes tipos de billetes.
Los 6 separadores son representados por barras y los 5 billetes por estrellas.
Solución
El número de formas de seleccionar 5 billetes corresponde al número de formar de ordenar 6 barras y 5 estrellas en una línea dando un total de 11 posiciones. Consecuentemente, el número de formas para seleccionar los 5 billetes es el número de formas para seleccionar la posición de las 5 estrellas desde las 11 posiciones. Esto corresponde al número de selecciones no ordenadas de 5 objetos en un conjunto de 11 objetos, que pueden hacerse de C(11,5) formas.
Entonces, hay
C(11,5) = 11! / (5!6!) = 464
formas de elegir 5 billetes desde una caja con 7 tipos de billetes.
Teorema
Hay C(n+r-1, r) = C(n+r-1, n-1)
r-combinaciones de un conjunto con n
elementos cuando la repetición de elementos
se permite.
Ejercicio
Suponga que una tienda de venta de galletas
tiene 4 tipos diferentes de galletas. ¿Cuántas
formas diferentes se pueden elegir 6
galletas? Asume que solo el tipo de galleta, y
no la galleta individual o el orden en el cual
son elegidas, importa.
Solución
C(9,6) = C(9,3) = 9*8*7/1*2*3 = 84
Existen 84 formas diferentes para elegir las 6
galletas.
Ejercicio
¿Cuántas soluciones tiene la ecuación,
x1 + x2 + x3 = 11
si x1, x2, y x3 son enteros positivos?
Para contar el número de soluciones, notamos que una solución corresponde a una forma de seleccionar 11 elementos desde un conjunto con 3 elementos así que x1 elementos de tipo uno, x2 elementos de tipo 2 y x3 elementos de tipo tres son elegidos. Así, el número de soluciones es igual al número de 11-combinaciones con repetición permitida desde un conjunto con tres elementos. Entonces:
C(3+11-1, 11) )=C(13,11) = C(13,2) = 13*12 / 1*2 = 78.
El número de soluciones de esta ecuación también se pueden encontrar cuando las variables están sujetas a restricciones.
Por ejemplo, podemos encontrar el número de soluciones donde las variables son enteros con x1 >=1, x2 >=2, y x3>=3.
Una solución a la ecuación sujeta a estas restricciones corresponde a una selección de 11 elementos con x1 elementos de tipo uno, x2 elementos de tipo 2, y x3 elementos de tipo 3, donde, además, existen al menos un elemento de tipo uno, dos elementos de tipo 2 y tres elementos de tipo 3.
Así, una solución corresponde a elegir de un elemento de tipo uno, dos de tipo dos y tres de tipo tres, junto con una elección de 5 elementos adicionales de cualquier tipo.
Por el teorema anterior, esto se puede hacer en C(3+ 5 -1, 5) = C(7, 5) = C(7, 2) = 7*6 / 1*2 = 21 formas.
Existen 21 soluciones de la ecuación sujeta a las restricciones dadas.
Ejemplo ¿Cuál es el valor de k después de la ejecución de la siguiente
sección de código?
Note que el valor inicial de k es 0 y que 1 es añadido en k cada ves que el ciclo anidado es recorrido con una secuencia de enteros i1, i2, …, im tal que 1 <= im <= im-1 <= … <= i1 <= n.
El número de tales secuencias de enteros es el número de formas para elegir m enteros de {1,2,.., n}, con repetición permitida. Utilizando el teorema, se obtiene que k= C(n+m-1, m) después de que el código fue ejecutado.
Ejercicio
¿Cuántas formas existen para seleccionar 3
elementos no ordenados desde un conjunto
con 5 elementos, cuando la repetición es
permitida?
Solución
C(3 + 5 -1 , 3) = C(7,3) = 35
Permutaciones con objetos indistinguibles
¿Cuántas cadenas diferentes se pueden formar al reordenar las letras de la palabra SUCCESS?
Como algunas de las letras de SUCCESS son las mismas, la respuesta no esta dada por el número de permutaciones de 7 letras. Estas palabras contienen tres Ss, dos Cs, una U, y una E. Para determinar el número de diferentes cadenas que pueden formarse al reordenar las letras, primero notamos que las tres Ss pueden colocarse en las siete posiciones es decir C(7,3) formas diferentes, dejando cuatro posiciones libres. Entonces las dos Cs pueden colocarse en C(4,2) formas, dejando dos posiciones libres. La U puede colocarse en C(2,1) formas, dejando sólo una posición libre. Consecuentemente, por la regla del producto, el número de diferentes cadenas que se pueden formar es:
Teorema 3
El número de diferentes permutaciones de n
objetos, donde hay n1 objetos indistinguibles
(idénticos) de tipo 1, n2 objetos
indistinguibles de tipo 2, …, y nk objetos
indistinguibles de tipo k, es
Objetos distinguibles y cajas distinguibles
Los objetos son cartas y las cajas son manos
de jugadores.
¿Cuántas formas existen para distribuir 5
cartas a cuatro jugadores, desde una baraja
de 52 cartas?
Teorema 4
El número de formas para distribuir n objetos
distinguibles en k cajas distinguibles así que
ni objetos son colocados en cajas i, i=1, 2,
…, k es igual a:
Otros ejemplos … Si se sientan 6 personas (A, B, C, D, E, F), alrededor de una mesa redonda, ¿cuántas
disposiciones (permutaciones) circulares distintas se pueden realizar si éstas se consideran iguales cuando una se puede obtener de otra por rotación?
Al considerar la figura a) y b), empezando en la parte superior del círculo y moviéndose en el sentido de las manecillas del reloj, se listan distintas disposiciones lineales ABEFCD y CDABEF, BEFCDA, DABEFC, EFCDAB y FCDABE, corresponden a la misma disposición circular que en a) o b).
Como cada disposición circular corresponde a 6 disposiciones lineales, se tiene que
6 * (número de disposiciones circulares de A,B,…, F) =
(número de disposiciones lineales de A, B, …, F)= 6!
En consecuencia, hay 6!/6 = 5!=120 disposiciones de A, B, …, F alrededor de la mesa circular.
Ahora, supóngase que las seis personas del ejemplo anterior son tres parejas, donde A, B y C son mujeres. Se quiere ordenar a las seis personas alrededor de la mesa de forma que se alternen los sexos. (Las disposiciones se consideran idénticas si una se puede obtener de la otra por rotación). Resolvamos el ejemplo anterior por otro método.
Si se coloca A en la mesa como se muestra la figura a), quedarán 5 lugares para ocupar. Ocupar estos lugares con B,C,…,F es el problema de permutar B,C,..,F linealmente, lo que puede hacerse de 5!=120 maneras.
Ahora situar a las 6 personas de forma que se alternen los sexos, considera A colocada en la figura b). La siguiente posición, a partir de A, se marca M1 (masculino) y puede colocarse de tres maneras. La posición F2 (femenino 2) puede ocuparse de 2 maneras. Procediendo de esta forma, por la regla del producto hay 3*2*2*1*1=12 maneras posibles de disponer a estas personas sin que dos hombres o dos mujeres se sienten juntos.