• Author / Uploaded
• Erick Sapon

Citation preview

Principios fundamentales del Conteo Semana 3 Matemática Discreta. Ing. Armando Gutiérrez

Combinaciones: El teorema del binomio • La baraja normal consta de 52 cartas con cuatro palos: tréboles, diamantes, corazones y espadas. • Cada palo tiene 13 cartas: as, 2 , 3 ------- , 9, 10, sota, reina y rey. • Si nos piden sacar tres cartas de una baraja normal, una tras otra y sin sustituirlas, entonces , por la regla del producto , existen 52! 52 ∗ 51 ∗ 50 = = 𝑃 52,3 49! • Posibilidades, una de las cuales es AC (as de corazones), 9T (nueve de tréboles), RD (rey de diamantes).

Combinaciones: El teorema del binomio • Si en vez de esto seleccionamos tres carta a la vez de modo que el orden de selección de las carta no ese importante, entonces las seis permutaciones AC-9T-RD,AC-RD-9T, 9T-AC-RD, 9T-RD-AC, RD-AC-9T, RD-9T-AC corresponden solo a una forma (no ordenada) se selección. En consecuencia cada selección o combinación de tres cartas, sin tener en cuenta el orden, corresponde a 3! Permutaciones de tres cartas. En forma de ecuación, esto se traduce como (3!) x (Numero de selecciones de tamaño tres de una baraja de 52)= Numero de permutaciones de tamaño 3 para las 52 cartas. 52! = 𝑃 52,3 = 49! • Por lo tanto, de una baraja estándar se pueden sacar tres cartas, sin reemplazo de 52!/(3!49!)=22,100 formas.

Combinaciones: El teorema del binomio

Combinaciones: El teorema del binomio • ¡Un buen consejo! Cuando se trata de un problema de conteo, debemos preguntarnos acerca de la importancia del orden en el problema. Cuando el orden es necesario, pensamos en términos de permutaciones y disposiciones y en la regla del producto. Cuando el orden no sea necesario, las combinaciones podrían tener un papel importante en la solución del problema.

Combinaciones: El teorema del binomio • Ejemplo 1: Miriam quiere dar una fiesta para algunos miembros de su comité de caridad. Debido al tamaño de su casa, sólo puede invitar a 11 de los 20 miembros de su comité. El orden no es importante, de modo que puede invitar a los “11 20 afortunados” de C (20,11) = = 20!(11!9!) = 167,960 formas. 11 Sin embargo, una vez que lleguen los 11, la forma en que ella los siente en tomo de su mesa rectangular es un problema de disposiciones. Por desgracia, ninguna parte de la teoría de combinaciones y permutaciones puede ayudar a la anfitriona con los “9 ofendidos" que no fueron invitados.

Combinaciones: El teorema del binomio • Ejemplo 2: a. Un estudiante que realiza un examen de historia recibe la instrucción de responder siete de 10 preguntas. Aquí no importa el orden, por lo que el estudiante puede responder el examen de 10! 10 = = 120 𝑓𝑜𝑟𝑚𝑎𝑠. 7 7! 3! b. Si el estudiante debe responder tres preguntas de las primeras cinco y cuatro de las últimas cinco, puede elegir tres preguntas de las 5 primeras cinco de = 10 formas, y elegir las otras cuatro preguntas 3 5 de = 5 formas. De modo que, por la regla del producto, el 4 5 5 estudiante puede realizar el examen = 10 x 5 = 50 formas. 3 4

Combinaciones: El teorema del binomio c. Por último, si las indicaciones del examen dicen que debe responder siete de las 10 preguntas, de las cuales al menos tres deberán ser de las primeras cinco, hay tres casos por considerar: i.

El estudiante responde tres de las primeras cinco preguntas y cuatro de las 5 5 últimas cinco: por la regla del producto, esto puede ocurrir de = 10 x 3 4 5 = 50 formas, como en la parte (b).

ii.

El estudiante elige cuatro de las primeras cinco preguntas y tres de las 5 5 últimas cinco: esto puede nacerse de = 5 x 10 = 50 formas, de 4 3 nuevo, usando la regla del producto.

iii.

El estudiante decide responder las cinco primeras preguntas y dos de las últimas cinco: la regla del producto indica que este último caso puede 5 5 ocurrir = 1 x 10 = 10 formas. 5 2

Combinaciones: El teorema del binomio • Si combinamos los resultados de los casos (i), (ii) y (iii). por la regla de la suma tenemos que el estudiante puede hacer 5 5 5 5 5 5 + + = 50 + 50 + 10 = 110 selecciones de 3 4 5 2 4 3 siete (de 10) preguntas, cada una de las cuales incluye al menos tres de las primeras cinco preguntas. • Ejemplo 3: a. En una escuela secundaria, la maestra de gimnasia debe elegir a nueve estudiantes de segundo y tercer año para el equipo de voleibol femenino. Si hay 28 jóvenes en segundo y 25 en 53 tercero, ella puede hacer la elección de = 4,431,613.550 9 formas,

Combinaciones: El teorema del binomio b. Si dos estudiantes de segundo y una de tercero son las mejores rematadoras y deben estar en el equipo, entonces el resto del 50 equipo podrá elegirse de = 15,890,700 formas. 6 c. Para cierto torneo, el equipo debe tener cuatro estudiantes de segundo y cinco de tercero. La maestra puede elegir a las 28 cuatro estudiantes de segundo de formas. Para cada una 4 25 de estas selecciones, ella tiene formas de elegir a las cinco 5 estudiantes de tercero. Por lo tanto, por la regla del producto, 28 25 puede elegir su equipo de = 1,087,836,750 formas 4 5 para ese torneo particular.

Combinaciones: El teorema del binomio • Algunos problemas se pueden analizar desde el punto de vista de las disposiciones o de las combinaciones, según la forma en que se examine la situación. El siguiente ejemplo demuestra esto. • Ejemplo 4: • La maestra del ejemplo 3 debe formar cuatro equipos de voleibol, de nueve mujeres cada uno, con las 36 estudiantes de primer año de su curso de educación física. ¿De cuántas formas puede elegir esos cuatro equipos? Los equipos se llaman A, B, C y D.

Combinaciones: El teorema del binomio a. Para formar el equipo A, puede elegir a nueve mujeres de las 36 36, de formas. Para el equipo B, el proceso de selección 9 27 18 9 proporciona posibilidades. Esto deja y formas 9 9 9 posibles de seleccionar los equipos C y D, respectivamente. Así, por la regla del producto, los cuatro equipos se pueden elegir de

36 9

27 9

18 9

36! 9 = = 2.145x1019 formas. 9!9!9!9! 9

Combinaciones: El teorema del binomio b. Para una solución alternativa, consideremos que las 36 estudiantes están alineadas como sigue:

• Para seleccionar los cuatro equipos, debemos distribuir nueve letras A, nueve B, nueve C y nueve D en los 36 espacios. El número de formas en que se pueden hacer estos es el número de disposiciones de 36 letras que comprenden nueve de cada una de las letras A, B, C y D. Este es ahora conocido problema de disposiciones de objetos no distintos, y la respuesta es 36! 𝑐𝑜𝑚𝑜 𝑒𝑛 𝑙𝑎 𝑝𝑎𝑟𝑡𝑒 𝑎 9! 9! 9! 9!

Combinaciones: El teorema del binomio • Nuestros siguientes ejemplos muestra que algunos problemas necesitan los conceptos de disposiciones y combinaciones para obtener las soluciones.

• Ejemplo 5: • El número de disposiciones de las letras de TALLAHASSEE es 11! = 831,600. 3! 2! 2! 2! 1! 1! • ¿Cuántas de estas disposiciones no tienen letras A adyacentes?

Combinaciones: El teorema del binomio • Cuando no tomamos en cuenta las letras A, existen 8! = 5040 2! 2! 2! 1! 1! • Formas de arreglar las letras restantes. Una de estas 5040 formas se muestra en la siguiente figura, donde las fechas que van hacia arriba indican nueve posiciones posibles para las letras A.

9 • Tres de estas disposiciones no pueden elegir de = 84 𝑓𝑜𝑟𝑚𝑎𝑠; y debido a 3 esto también es posible para las restantes 5039 disposiciones de E, E, S, T, L, L, S, H, por la regla del producto existen 5040 x 84 = 423,360 disposiciones de las letras de TALLAHASSEE sin letra A consecutivas.

Combinaciones con repetición: Distribuciones • Cuando se permite las repeticiones, hemos visto que, para n objetos distintos, una disposición de tamaño r de estos objetos puede obtener de nr formas, para un entero ≥ 0. Ahora analizaremos el problema comparable para las combinaciones y de nuevo obtendremos un problema relacionado con el anterior cuya solución se sigue de nuestro principio de conteo anteriores.

Combinaciones con repetición: Distribuciones • Ejemplo 6: • Al regresar a cada después de una practica de carrera en pista, siete estudiantes de bachillerato se detienen en un restaurante de comida rápida, donde cada una puede comer lo siguiente: una hamburguesa con queso, un hot-dog, un taco o un sándwich de atún. ¿Cuántas compras diferentes son posibles? • Sean q, h, t y p la hamburguesa con queso, el hot-dog, el taco y el sándwich de atún, respectivamente. Aquí nos interesa el número de artículos comprados y no el orden en que se adquirieron, de modo que el problema es de selecciones o combinaciones con repetición.

Combinaciones con repetición: Distribuciones • En la tabla 1.6 enumeramos algunas compras posibles en la columna (a) y otro medio de representar cada forma en la columna (b).

Combinaciones con repetición: Distribuciones • Para una compra de la columna (b) de la tabla 1.6, vemos que cada x a la izquierda de la primera barra (│) representa una q, cada x entre la primera y la segunda barras representa una h, las x entre la segunda y tercera barras representan t y todo x a la derecha de la tercera barra representa una p. Por ejemplo, la tercera compra tiene tres barras consecutivas, porque nadie compró un hot-dog ni un taco; la barra que está al principio de la cuarta compra indica que no se adquirieron hamburguesas con queso.

Combinaciones con repetición: Distribuciones • De nuevo, se ha establecido una correspondencia entre dos colecciones de objetos, en la que sabemos como contar el numero de una colección. Para las representaciones de la columna (b) de la tabla 1.6, estamos enumerando todas las disposiciones de 10 símbolos que constan de siete letras x y tres barras │, de modo que, por nuestra correspondencia, el número de órdenes diferentes por la columna (a) es 10! 10 = 7 7! 3!

Combinaciones con repetición: Distribuciones • En este ejemplo observamos que las siete letras X(una para cada estudiante) corresponden al tamaño de la selección y que las letras barras son necesarias para separar los 3 + 1 = 4 alimentos que se pueden elegir.

Combinaciones con repetición: Distribuciones • Ejemplo 7: • Una tienda ofrece 20 tipos de donas. Si suponemos que al menos hay una docena de cada tipo cuando entramos a la tienda, podemos elegir una docena de donas de C(20+121;12)=C(31,12)=141,120,525 formas. (En este caso, n=20, r=12) • Ejemplo 8:

• La presidenta Elena tiene cuatro vicepresidentas: (1) Beatriz, (2) Carmen, (3) María Luisa y (6 ) Mónica. Elena desea distribuir entre ellas $1,000 en cheques de gratificación en navidad; cada cheque será expedido por un múltiplo de $100.

Combinaciones con repetición: Distribuciones a. Si se admite el caso en que una o mas de las vicepresidentas no obtenga nada, la presidenta Elena hace una selección de tamaño 10 (uno por cada unidad de $100) de una colección de tamaño 4 (cuatro vicepresidentas), con repetición. Esto puede hacerse de C(4+10-1,10)=C(13,10)=286 formas. b. Si dese que no haya resentimientos, cada vicepresidenta debe cumplir al menos $100. Con esta restricción, la presidenta Elena debe hacer ahora una selección de tamaño 6 (las restantes seis unidades de $100) de la misma colección de tamaño 4, y las opciones son ahora C(4+6-1,6)=C(9,6)=84. [Por ejemplo, en este caso, la opción 2,3,3,4,4,4 se interpreta así: Beatriz no recibe nada adicional, ya que no hay ningún 1 en la opción. El 2 de la selección indica que Carmen recibe $100 adicionales. María Luisa recibe $200 adicionales, $100 por cada un de los dos 3 que hay en la selección. Debido a los tres 4, el cheque de gratificación de Mónica es de $100 + 3($100)=$400]

Combinaciones con repetición: Distribuciones c. Si cada vicepresidenta debe recibir al menos $100 y Mónica, vicepresidenta ejecutiva, recibe al menos $500, entonces el número de formas en que la presidenta Elena puede distribuir los cheques de gratificación es

• Habiendo trabajado ya con estos ejemplos de combinaciones con repetición, analizaremos ahora dos ejemplos relativos a otros principios de conteo.

Combinaciones con repetición: Distribuciones • Ejemplo 9: • ¿De cuántas formas podemos distribuir siete manzanas y seis naranjas entre cuatro niños, de modo que cada uno reciba al menos una manzana? • Al dar a cada niño una manzana, tenemos C(4+3-1,3)=20 formas de distribuir las otras manzanas y C(4+6-1,6)=84 formas de distribuir las seis naranjas. Así, por la regla del producto, hay 20 x 84 = 1680 formas de distribuir la fruta en las condiciones dadas.

Combinaciones con repetición: Distribuciones • Ejemplo 10: • Un mensaje está formado por 12 símbolos diferentes y se va a transmitir a través de un canal de comunicación. Además de los 12 símbolos, el transmisor también enviara un total de 45 espacios en blanco entre los símbolos, usando al menos tres espacios entre cada par de símbolos consecutivos. ¿De cuántas formas puede el transmisor enviar ese mensaje?. • Hay 12! Formas de colocar los 12 símbolos diferentes y para cualquiera de estas disposiciones hay 11 posiciones entre los 12 símbolos. Debido a que debe haber al menos tres espacios entre los símbolos consecutivos, utilizaremos hasta 33 de los 45 espacios y distribuimos los 12 espacios restantes. Esta es entonces una selección, con repetición, de tamaño 12 (los espacios) de una colección de tamaño 11 (las posiciones), y puede realizarse de C(11+12-1,12)=646,646 formas. • En consecuencia, por la regla del producto, el transmisor puede enviar tales 22 mensajes con el espacio necesario de (12!) = 3097 𝑥 1014 formas. 12

Combinaciones con repetición: Distribuciones • En el siguiente ejemplo se introduce una idea que parece tener más que ver con la teoría de números que con las combinaciones o las disposiciones. Sin embargo, la solución de este ejemplo será equivalente al conteo de las combinaciones con repetición. • Ejemplo 10: • Determine todas las soluciones enteras de la ecuación x1+x2+x3+x4=7, donde xi ≥ 0

para toda 1 ≤ i ≤ 4.

Combinaciones con repetición: Distribuciones • Una solución de la ecuación es x1= 3, x2=3, x3=0, x4=1. (Esto es diferente de una solución del tipo x1= 1, x2=0, x3=3, x4=3, aunque se utilicen los mismos cuatro enteros). Una posible interpretación de la solución x1= 3, x2=3, x3=0, x4=1 es que estamos distribuyendo siete monedas (objetos idénticos) entre cuatro niños (recipientes diferentes), y que hemos dado tres monedas a cada una de los dos primeros niños, nada al tercero y la ultima moneda al cuarto niño. Si seguimos con esta interpretación, vemos que cada solución entera no negativa de las ecuaciones corresponde a una selección, con repetición, de tamaño 7 (las monedas idénticas) de una colección de tamaño 4 (los niños distintos), de modo que hay C(4+7-1,7)=120 soluciones.

Combinaciones con repetición: Distribuciones

• En términos de distribuciones, la parte (c) es válida solo cuando los r objetos que se distribuyen son idénticos y los n recipientes son distintos. Cuando los r objetos y los n recipientes son distintos, podemos elegir cualquiera de los n recipientes para cada una de los objetos y obtener n distribuciones mediante la regla del producto.

Combinaciones con repetición: Distribuciones • Cuando los objetos son distintos pero los recipientes son idénticos, resolvemos el problema mediante los números de Stirling de segundo tipo. Para el último caso, cuando los objetos y los recipientes son idéntico, la teoría de particiones de los enteros nos dará algunos resultados necesarios. • Ejemplo 11: • ¿De cuántas formas se puede distribuir 10 canicas blancas (idénticas) en seis recipientes diferentes?

Combinaciones con repetición: Distribuciones • La solución de este problema es equivalente a determinar el número de soluciones enteras no negativas de la ecuación x1+x2+…..+x6=10. Ese número es la cantidad de selecciones de tamaño 10, con repetición, de una colección de tamaño 6. Por lo tanto, la respuesta es C(6+10-1,10)=3003.