1.E: Conteo (Ejercicios)

Template:MathJaxLevin

1.1: Principios Aditivos y Multiplicativos

1

Tu armario consta de 5 camisas, 3 pares de pantalones y 17 pajaritas. ¿Cuántos atuendos diferentes puedes hacer?

Responder

Hay 255 atuendos. Utilizar el principio multiplicativo.

2

Para tu entrevista universitaria, debes llevar corbata. Tienes 3 corbatas regulares (aburridas) y 5 pajaritas (geniales).

1. ¿Cuántas opciones tienes para tu ropa de cuello?
2. Te das cuenta que la entrevista es para la universidad de payasos, así que probablemente deberías usar tanto una corbata normal como una pajarita. ¿Cuántas opciones tienes ahora?
3. Para el resto de tu atuendo, tienes 5 camisas, 4 faldas, 3 pantalones y 7 vestidos. Quieres seleccionar ya sea una camisa para llevar con falda o pantalón, o simplemente un vestido. ¿Cuántos atuendos tienes para elegir?

Responder

1. 8 corbatas. Utilice el principio aditivo.
2. 15 corbatas. Utilizar el principio multiplicativo
3. \(5 \cdot (4+3) + 7 = 42\)atuendos.

3

Tu colección de Blu-ray consta de 9 comedias y 7 películas de terror. Dé un ejemplo de una pregunta para la que la respuesta es:

1. 16.
2. 63.

Responder

1. Por ejemplo, 16 es el número de opciones que tienes si quieres ver una película, ya sea una película de comedia o de terror.
2. Por ejemplo, 63 es el número de opciones que tienes si vas a ver dos películas, primero una comedia y luego una de terror.

4

Normalmente escribimos números en forma decimal (o base 10), es decir, los números se componen usando 10 “dígitos” diferentes\(\{0,1,\ldots, 9\}\text{.}\) A veces aunque es útil escribir números hexadecimales o base 16. Ahora hay 16 dígitos distintos que se pueden usar para formar números:\(\{0, 1, \ldots, 9, \mathrm{A, B, C, D, E, F}\}\text{.}\) Entonces, por ejemplo, un número hexadecimal de 3 dígitos podría ser 2B8.

1. ¿Cuántos hexadecimales de 2 dígitos hay en los que el primer dígito es E o F? Explica tu respuesta en términos del principio aditivo (usando eventos o conjuntos).
2. Explica por qué tu respuesta a la parte anterior es correcta en términos del principio multiplicativo (usando eventos o conjuntos). ¿Por qué tanto los principios aditivos como los multiplicativos te dan la misma respuesta?
3. ¿Cuántos hexadecimales de 3 dígitos comienzan con una letra (A-F) y terminan con un numeral (0-9)? Explique.
4. ¿Cuántos hexadecimales de 3 dígitos comienzan con una letra (A-F) o terminan con un numeral (0-9) (o ambos)? Explique.

5

Supongamos que tienes conjuntos\(A\) y\(B\) con\(\card{A} = 10\) y\(\card{B} = 15\text{.}\)

1. ¿Cuál es el mayor valor posible para\(\card{A \cap B}\text{?}\)
2. ¿Cuál es el valor más pequeño posible para\(\card{A \cap B}\text{?}\)
3. ¿Cuáles son los valores posibles para\(\card{A \cup B}\text{?}\)

Responder

1. Para maximizar el número de elementos en común entre\(A\) y\(B\text{,}\) hacer\(A \subset B\text{.}\) Esto daría\(\card{A \cap B} = 10\text{.}\)
2. \(A\)y\(B\) podría no tener elementos en común, dando\(\card{A\cap B} = 0\text{.}\)
3. \(15 \le \card{A \cup B} \le 25\text{.}\)De hecho, cuando\(\card{A \cap B} = 0\) entonces\(\card{A \cup B} = 25\) y cuando\(\card{A \cap B} = 10\) entonces\(\card{A \cup B} = 15\text{.}\)

6

Si\(\card{A} = 8\) y\(\card{B} = 5\text{,}\) qué es\(\card{A \cup B} + \card{A \cap B}\text{?}\)

Responder

\(\card{A \cup B} + \card{A \cap B} = 13\text{.}\)Usa PIE: sabemos\(\card{A \cup B} = 8 + 5 - \card{A \cap B}\text{.}\)

7

A un grupo de estudiantes universitarios se les preguntó sobre sus hábitos de ver televisión. De los encuestados, 28 estudiantes ven The Walking Dead, 19 miran The Blacklist y 24 miran Game of Thrones. Además, 16 ven The Walking Dead y The Blacklist, 14 miran The Walking Dead y Game of Thrones, y 10 miran The Blacklist y Game of Thrones. Hay 8 alumnos que ven los tres espectáculos. ¿Cuántos alumnos encuestados vieron al menos uno de los programas?

Responder

39 alumnos. Use PIE o un diagrama de Venn.

8

En una encuesta reciente, 30 estudiantes informaron si les gustaban sus papas Puré, francés frito o horneado dos veces. A 15 les gustó el puré, a 20 les gustaban las papas fritas y a 9 les gustaban las papas dos veces al horno. Además, a 12 estudiantes les gustó tanto el puré como las papas fritas, a 5 les gustaban las papas fritas y las papas dos veces al horno, a 6 les gustaba el puré y al horno, y a 3 les gustaban los ¿Cuántos estudiantes odian las papas? Explica por qué tu respuesta es correcta.

9

¿Para cuántos\(n \in \{1,2, \ldots, 500\}\) es\(n\) un múltiplo de uno o más de 5, 6 o 7?

Pista:

Para saber cuántos números son divisibles por 6 y 7, por ejemplo, toma\(500/42\) y redondea hacia abajo.

10

Dejar\(A\text{,}\)\(B\text{,}\) y\(C\) ser conjuntos.

1. Encuentre\(\card{(A \cup C)\setminus B}\) siempre\(\card{A} = 50\text{,}\)\(\card{B} = 45\text{,}\)\(\card{C} = 40\text{,}\)\(\card{A\cap B} = 20\text{,}\)\(\card{A \cap C} = 15\text{,}\)\(\card{B \cap C} = 23\text{,}\) y\(\card{A \cap B \cap C} = 12\text{.}\)
2. Describir un conjunto en términos de\(A\text{,}\)\(B\text{,}\) y\(C\) con cardinalidad 26.

11

Considere todas las 5 letras “palabras” hechas de las letras\(a\) a través de\(h\text{.}\) (Recordemos, las palabras son solo cadenas de letras, no necesariamente palabras reales en inglés).

1. ¿Cuántas de estas palabras hay en total?
2. ¿Cuántas de estas palabras no contienen letras repetidas?
3. ¿Cuántas de estas palabras empiezan con la subpalabra “aha”?
4. ¿Cuántas de estas palabras empiezan con “aha” o terminan con “bah” o ambas?
5. ¿Cuántas de las palabras que no contienen repeticiones tampoco contienen la subpalabra “malo”?

Responder

1. \(8^5 = 32768\)palabras, ya que seleccionas entre 8 letras 5 veces.
2. \(8\cdot 7\cdot 6\cdot 5\cdot 4 = 6720\)palabras. Después de seleccionar una letra, tienes menos letras para seleccionar para la siguiente.
3. \(8 \cdot 8 =64\)palabras: es necesario seleccionar las letras 4ª y 5ª.
4. \(64 + 64 - 0 = 128\)palabras. Hay 64 palabras que comienzan con “aha” y otras 64 palabras que terminan con “bah”. Quizás contamos en exceso las palabras que ambas empiezan con “aha” y terminan con “bah”, pero como las palabras sólo tienen 5 letras de largo, no existen tales palabras.
5. \((8\cdot 7\cdot 6\cdot 5\cdot 4) - 3\cdot (5\cdot 4) = 6660\)palabras. Todas las palabras menos las malas. La palabra tabú puede estar en cualquiera de tres posiciones (comenzando con la letra 1, 2 o 3) y para cada posición debemos elegir las otras dos letras (de las 5 letras restantes).

12

¿Para cuántos números de tres dígitos (100 a 999) es par la suma de los dígitos? (Por ejemplo,\(343\) tiene una suma par de dígitos:\(3+4+3 = 10\) que es par.) Encuentra la respuesta y explica por qué es correcta de al menos dos formas diferentes.

13

El número 735000 factores como\(2^3 \cdot 3 \cdot 5^4 \cdot 7^2\text{.}\) ¿Cuántos divisores tiene? Explica tu respuesta usando el principio multiplicativo.

1.2: Coeficientes binomiales

1

Let\(S = \{1, 2, 3, 4, 5, 6\}\)

1. ¿Cuántos subconjuntos hay en total?
2. ¿Cuántos subconjuntos tienen\(\{2,3,5\}\) como subconjunto?
3. ¿Cuántos subconjuntos contienen al menos un número impar?
4. ¿Cuántos subconjuntos contienen exactamente un número par?

Responder

1. \(2^6 = 64\)subconjuntos. Necesitamos seleccionar sí/no para cada uno de los seis elementos.
2. \(2^3 = 8\)subconjuntos. Necesitamos seleccionar sí/no para cada uno de los tres elementos restantes.
3. \(2^6 - 2^3 = 56\)subconjuntos. Hay 8 subconjuntos que no contienen ningún número impar (seleccione sí/no para cada número par).
4. \(3\cdot 2^3 = 24\)subconjuntos. Primero escoge el número par. Entonces di sí o no a cada uno de los números impares.

2

Let\(S = \{1, 2, 3, 4, 5, 6\}\)

1. ¿Cuántos subconjuntos hay de cardinalidad 4?
2. ¿Cuántos subconjuntos de cardinalidad 4 tienen\(\{2,3,5\}\) como subconjunto?
3. ¿Cuántos subconjuntos de cardinalidad 4 contienen al menos un número impar?
4. ¿Cuántos subconjuntos de cardinalidad 4 contienen exactamente un número par?

Responder

1. \({6\choose 4} = 15\)subconjuntos.
2. \({3 \choose 1} = 3\)subconjuntos. Necesitamos seleccionar 1 de los 3 elementos restantes para estar en el subconjunto.
3. \({6 \choose 4} = 15\)subconjuntos. Todos los subconjuntos de cardinalidad 4 deben contener al menos un número impar.
4. \({3 \choose 1} = 3\)subconjuntos. Selecciona 1 de los 3 números pares. Los tres números impares restantes de\(S\) deben estar todos en el conjunto.

3

Let\(A = \{1,2,3,\ldots,9\}\text{.}\)

1. ¿Cuántos subconjuntos\(A\) hay? Es decir, encuentra\(|\pow(A)|\text{.}\) Explique.
2. ¿Cuántos subconjuntos de\(A\) contienen exactamente 5 elementos? Explique.
3. ¿Cuántos subconjuntos de\(A\) contienen solo números pares? Explique.
4. ¿Cuántos subconjuntos de\(A\) contienen un número par de elementos? Explique.

4

\(9\)¿Cuántas cadenas de bits (es decir, cadenas de bits de longitud 9) hay que:

1. Empezar con la sub-cadena 101? Explique.
2. ¿Tiene peso 5 (es decir, contener exactamente cinco 1) y comenzar con la sub-cadena 101? Explique.
3. ¿Empezar con\(101\) o terminar con\(11\) (o ambos)? Explique.
4. ¿Tiene peso 5 y ya sea comenzar con 101 o terminar con 11 (o ambos)? Explique.

5

Rompes tu alcancía para descubrir muchos centavos y cinco centavos. Empiezas a organizar estos en filas de 6 monedas.

1. Te encuentras haciendo filas que contienen el mismo número de centavos y monedas de cinco centavos. Por diversión, decides establecer cada fila posible de este tipo. ¿Cuántas monedas vas a necesitar?
2. ¿Cuántas monedas necesitarías para hacer todas las filas posibles de 6 monedas (no necesariamente con igual número de centavos y monedas de cinco centavos)?

Responder

1. Podemos pensar en cada fila como una cadena de 6 bits de peso 3 (ya que de las 6 monedas, requerimos 3 para ser centavos). Así hay\({6 \choose 3} = 20\) filas posibles. Cada fila requiere 6 monedas, así que si queremos hacer todas las filas al mismo tiempo, necesitaremos 120 monedas (60 de cada una).
2. Ahora hay\(2^6 = 64\) filas posibles, que es también\({6 \choose 0} + {6\choose 1} + {6 \choose 2} + {6 \choose 3} + {6 \choose 4} + {6 \choose 5} + {6 \choose 6}\text{,}\) si las divides en filas que contienen 0, 1, 2, etc. centavos. Así necesitamos\(6 \cdot 64 = 384\) monedas (192 de cada una).

6

¿Cuántas cadenas de 10 bits contienen 6 o más 1's?

Responder

\({10 \choose 6} + {10\choose 7} + {10\choose 8} + {10 \choose 9} + {10\choose 10} = 386\)cuerdas. Contar el número de cadenas con cada número permisible de 1's por separado, luego sumarlas.

7

¿Cuántos subconjuntos de\(\{0,1,\ldots, 9\}\) tienen cardinalidad 6 o más?

Pista:

Romper la pregunta en cinco casos.

8

¿Cuál es el coeficiente de\(x^{12}\) in\((x+2)^{15}\text{?}\)

Responder

Para conseguir una\(x^{12}\text{,}\) debemos escoger 12 de los 15 factores para contribuir un\(x\text{,}\) dejando los otros 3 para aportar un 2. Hay\({15 \choose 12}\) formas de seleccionar estos 12 factores. Entonces el término que contiene un\(x^{12}\) será\({15 \choose 12}x^{12}2^{3}\text{.}\) En otras palabras, el coeficiente de\(x^{12}\) es\({15\choose 12}2^3 = 3640\text{.}\)

9

¿Cuál es el coeficiente de\(x^9\) en la expansión de\((x+1)^{14} + x^3(x+2)^{15}\text{?}\)

10

¿Cuántas trayectorias de celosía más cortas comienzan en (3,3) y

1. terminar en (10,10)?
2. terminar en (10,10) y pasar a través de (5,7)?
3. terminar en (10,10) y evitar (5,7)?

Responder

1. \({14 \choose 7} = 3432\)caminos. Todos los caminos tienen una longitud 14 (7 escalones hacia arriba y 7 pasos a la derecha), solo seleccionamos cuáles 7 de esos 14 deben estar arriba.
2. \({6 \choose 2}{8\choose 5} = 840\)caminos. Primero viaja a (5,7), y luego continuar hasta (10,10).
3. \({14 \choose 7} - {6\choose 2}{8 \choose 5}\)caminos. Elimina todos los caminos que encontraste en la parte (b).

11

Gridtown USA, además de tener excelentes tiendas de donas, es conocido por su cuadrícula de calles y avenidas precisamente trazada. Las calles corren de este a oeste, y avenidas norte-sur, para todo el tramo del pueblo, nunca curvadas y nunca interrumpidas por parques o escuelas o similares.

Supongamos que vive en la esquina de 1º y 1º y trabaja en la esquina de 12 y 12. Así debes recorrer 22 cuadras para ponerte a trabajar lo más rápido posible.

1. ¿Cuántas rutas diferentes puedes tomar para trabajar, asumiendo que quieres llegar lo más rápido posible?
2. Ahora suponga que quiere parar y obtener una rosquilla de camino al trabajo, de su tienda de donas favorita en la esquina de 8th st y 10th ave. ¿Cuántas rutas para trabajar, a través de la tienda de donas, puedes tomar (nuevamente, asegurando la ruta más corta posible)?
3. Desastre golpea Gridtown: hay un bache en la 4ta avenida entre las calles 5 y 6. ¿Cuántas rutas para trabajar puedes tomar evitando ese antiestético (y peligroso) tramo de carretera?
4. ¿Cuántas rutas hay tanto evitando el bache como visitando la tienda de donas?

12

Supongamos que está pidiendo una pizza grande de D.P. Masa. Quieres 3 coberturas distintas, elegidas de su lista de 11 coberturas vegetarianas.

1. ¿Cuántas opciones tienes para tu pizza?
2. ¿Cuántas opciones tienes para tu pizza si te niegas a tener piña como uno de tus ingredientes?
3. ¿Cuántas opciones tienes para tu pizza si insistes en tener piña como uno de tus coberturas?
4. ¿Cómo se relacionan entre sí las tres preguntas anteriores?

13

Explicar por qué el coeficiente de\(x^5y^3\) la misma como el coeficiente de\(x^3y^5\) en la expansión de\((x+y)^8\text{?}\)

1.3: Combinaciones y permutaciones

1

Una pizzería ofrece 10 coberturas.

1. ¿Cuántas pizzas de 3 topping podrían poner en su menú? Supongamos que no se permiten coberturas dobles.
2. ¿Cuántas pizzas totales son posibles, con entre cero y diez coberturas (pero no dobles coberturas) permitidas?
3. La pizzería enumerará los 10 aderezos en dos columnas de igual tamaño en su menú. ¿De cuántas maneras pueden organizar los coberturas en la columna de la izquierda?

Responder

1. \({10 \choose 3} = 120\)pizzas. Debemos elegir (sin ningún orden en particular) 3 de los 10 coberturas.
2. \(2^{10} = 1024\)pizzas. Di sí o no a cada topping.
3. \(P(10,5) = 30240\)maneras. Asigne cada uno de los 5 puntos de la columna de la izquierda a una cobertura única para pizza.

2

Una cerradura de combinación consiste en una esfera con 40 números en él. Para abrir la cerradura, giras el dial a la derecha hasta llegar a un primer número, luego a la izquierda hasta llegar al segundo número, luego a la derecha nuevamente al tercer número. Los números deben ser distintos. ¿Cuántas combinaciones diferentes son posibles?

Responder

A pesar de su nombre, no estamos buscando una combinación aquí. El orden en que aparecen los tres números importa. Existen\(P(40,3) = 40\cdot 39 \cdot 38\) diferentes posibilidades para la “combinación”. Esto es asumiendo que no puedes repetir ninguno de los números (si pudieras, la respuesta sería\(40^3\)).

3

Usando los dígitos 2 a 8, encuentre el número de diferentes números de 5 dígitos de tal manera que:

1. Los dígitos se pueden usar más de una vez.
2. Los dígitos no se pueden repetir, pero pueden venir en cualquier orden.
3. Los dígitos no pueden repetirse y deben escribirse en orden creciente.
4. ¿Cuál de las preguntas de conteo anteriores es una combinación y cuál es una permutación? Explique por qué esto tiene sentido.

4

¿Cuántos triángulos hay con vértices de los puntos que se muestran a continuación? Tenga en cuenta que no estamos permitiendo triángulos degenerados, unos con los tres vértices en la misma línea, pero sí permitimos triángulos no rectos. Explica por qué tu respuesta es correcta.

Pista:

Necesitas exactamente dos puntos en el eje\(x\) - o\(y\) -eje, pero no sobrecuentes los triángulos rectos.

5

¿Cuántos cuadriláteros puedes dibujar usando los puntos de abajo como vértices (esquinas)?

Responder

\({7\choose 2}{7\choose 2} = 441\)cuadriláteros. Debemos escoger dos de los siete puntos de la fila superior y dos de los siete puntos de la fila inferior. Sin embargo, no hace diferencia cuál de los dos (en cada fila) elegimos primero porque una vez que se seleccionan estos cuatro puntos, hay exactamente un cuadrilátero que determinan.

6

Cuantos de los cuadriláteros posibles en el problema anterior son:

1. ¿Cuadrados?
2. ¿Rectángulos?
3. ¿Paralelogramos?
4. ¿Trapecios? ² Aquí, como en el cálculo, un trapecio se define como un cuadrilátero con al menos un par de lados paralelos. En particular, los paralelogramos son trapezoides.
5. ¿Trapezoides que no son paralelogramos?

Responder

1. 5 cuadrados. Necesitas saltarte exactamente un punto en la parte superior y en la parte inferior para que las longitudes laterales sean iguales. Una vez que eliges un punto en la parte superior, se determinan los otros tres puntos.
2. \({7 \choose 2}\)rectángulos. Una vez que seleccionas los dos puntos en la parte superior, se determinan los dos inferiores.
3. Esto es complicado ya que debes preocuparte por quedarte sin espacio. Una forma de contar: irrumpir en casos por la ubicación de la esquina superior izquierda. Obtienes\({7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) = 91\) paralelogramos.
4. Todos ellos
5. \({7\choose 2}{7\choose 2} - \left[ {7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) \right]\text{.}\)Todos ellos, excepto los paralelogramos.

7

Un anagrama de una palabra no es más que un reordenamiento de sus letras. ¿Cuántos anagramas diferentes de “incopyrightable” hay? (Esta resulta ser la palabra común más larga en inglés sin letras repetidas).

8

¿Cuántos anagramas hay de la palabra “evalúa” que empiezan por la letra “a”?

Responder

Después de la primera letra (a), debemos reorganizar las 7 letras restantes. Solo hay dos letras (s y e), así que esto es realmente solo una pregunta de cadena de bits (piense en s como 1 y e como 0). Así hay\({7 \choose 2} = 21\) anagramas comenzando con “a”.

9

¿Cuántos anagramas hay de “anagrama”?

10

En un retiro de negocios, tu empresa de 20 empresarios y empresarias va al golf.

1. Es necesario dividir en cuarteto (grupos de 4 personas): un primer cuarteto, un segundo cuarteto, y así sucesivamente. ¿De cuántas maneras puedes hacer esto?
2. Después de todo tu arduo trabajo, te das cuenta de que de hecho, quieres que cada cuarteto incluya a uno de los cinco miembros de la Junta Directiva. ¿De cuántas maneras puedes hacer esto?

Responder

1. \({20 \choose 4}{16 \choose 4}{12 \choose 4}{8 \choose 4}{4 \choose 4}\)maneras. Elige 4 de 20 personas para estar en el primer cuarteto, luego 4 de las 16 restantes para el segundo cuarteto, y así sucesivamente (usa el principio multiplicativo para combinar).
2. \(5!{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}\)maneras. Primero determine el tiempo de salida de los 5 miembros de la junta, luego seleccione 3 de los 15 no miembros de la junta para jugar al golf con el primer miembro de la junta, luego 3 de los 12 restantes para jugar al golf con el segundo, y así sucesivamente.

11

¿Cuántos arreglos de asientos diferentes son posibles para el Rey Arturo y sus 9 caballeros alrededor de su mesa redonda?

Responder

\(9!\)(hay 10 personas sentadas alrededor de la mesa, pero no importa dónde se siente el rey Arturo, sólo quién se sienta a su izquierda, dos asientos a la izquierda, y así sucesivamente).

12

Considera conjuntos\(A\) y\(B\) con\(|A| = 10\) y\(|B| = 17\text{.}\)

1. ¿Cuántas funciones\(f: A \to B\) hay?
2. ¿Cuántas funciones\(f: A \to B\) son inyectivas?

Responder

1. \(17^{10}\)funciones. Hay 17 opciones para la imagen de cada elemento en el dominio.
2. \(P(17, 10)\)funciones inyectoras. Hay 17 opciones para la imagen del primer elemento del dominio, luego solo 16 opciones para el segundo, y así sucesivamente.

13

Considerar funciones\(f: \{1,2,3,4\} \to \{1,2,3,4,5,6\}\text{.}\)

1. ¿Cuántas funciones hay en total?
2. ¿Cuántas funciones son inyectivas?
3. ¿Cuántas de las funciones inyectoras están aumentando? Estar aumentando significa que si\(a \lt b\) entonces\(f(a) \lt f(b)\text{,}\) o en otras palabras, las salidas se hacen más grandes a medida que las entradas se hacen más grandes.

14

Hemos visto que la fórmula para\(P(n,k)\) es\(\dfrac{n!}{(n-k)!}\text{.}\) Tu tarea aquí es explicar por qué esta es la fórmula correcta.

1. Supongamos que tienes 12 fichas, cada una de un color diferente. ¿Cuántas pilas diferentes de 5 fichas puedes hacer? Explica tu respuesta y por qué es lo mismo que usar la fórmula para\(P(12,5)\text{.}\)
2. Usando de nuevo el escenario de las 12 fichas, ¿qué\(12!\) cuenta? ¿Qué\(7!\) cuenta? Explique.
3. Explique por qué tiene sentido dividir\(12!\) por\(7!\) cuando se computa\(P(12,5)\) (en términos de los chips).
4. ¿Su explicación funciona para números distintos al 12 y al 5? Explicar la fórmula\(P(n,k) = \frac{n!}{(n-k)!}\) usando las variables\(n\) y\(k\text{.}\)

1.4: Pruebas combinatorias

1

Demostrar la identidad\({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\) usando una pregunta sobre subconjuntos.

Responder

Prueba

Pregunta: ¿Cuántos subconjuntos de tamaño\(k\) hay del conjunto?\(\{1,2,\ldots, n\}\text{?}\)

Respuesta 1: Debes elegir entre\(k\)\(n\) elementos para poner en el conjunto, lo cual se puede hacer de\({n \choose k}\) maneras.

Respuesta 2: Primero cuenta el número de subconjuntos\(k\) -elemento de los\(\{1,2,\ldots, n\}\) cuales contienen el número\(n\text{.}\) Debemos elegir\(k-1\) del\(n-1\) otro elemento a incluir en este conjunto. Por lo tanto\({n-1\choose k-1}\), existen tales subconjuntos. Aún no hemos contado todos los subconjuntos\(k\) -element de\(\{1,2,\ldots, n\}\) though. De hecho, nos hemos perdido exactamente esos subconjuntos que NO contienen\(n\text{.}\) Para formar uno de estos subconjuntos, tenemos que elegir\(k\) de los otros\(n-1\) elementos, así que esto se puede hacer de\({n-1 \choose k}\) maneras. Así la respuesta a la pregunta es\({n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

Ya que las dos respuestas son ambas respuestas tot eh misma pregunta, son iguales, estableciendo la identidad\({n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\)

\(\square\)

2

Dar una prueba combinatoria de la identidad\(2+2+2 = 3\cdot 2\text{.}\)

Responder

Prueba

Pregunta: ¿Cuántas palabras de 2 letras comienzan con a, b o c y terminan con y o z?

Respuesta 1: Hay dos palabras que comienzan con a, dos que comienzan con b, dos que comienzan con c, para un total de\(2+2+2\text{.}\)

Respuesta 2: Hay tres opciones para la primera letra y dos opciones para la segunda letra, para un total de\(3 \cdot 2\text{.}\)

Dado que las dos respuestas son ambas respuestas a una misma pregunta, son iguales. Así\(2 + 2 + 2 = 3\cdot 2\text{.}\)

\(\square\)

3

Dar una prueba combinatoria de la identidad\(1 + 2 + 3 + \cdots + n = {n+1 \choose 2}\text{.}\)

Responder

Prueba

Pregunta: ¿Cuántos subconjuntos de\(A = {1,2,3, \ldots, n+1}\) contienen exactamente dos elementos?

Respuesta 1: Debemos elegir 2 elementos de\(n+1\) las opciones, así que hay\({n+1 \choose 2}\) subconjuntos.

Respuesta 2: Desplegamos esta pregunta en casos, con base en cuál es el mayor de los dos elementos en el subconjunto. El elemento más grande no puede ser 1, ya que necesitamos al menos un elemento más pequeño que él.

El elemento más grande es 2: hay 1 opción para el elemento más pequeño.

El elemento más grande es 3: hay 2 opciones para el elemento más pequeño.

El elemento más grande es 4: hay 3 opciones para el elemento más pequeño.

Y así sucesivamente. Cuando el elemento más grande es\(n+1\text{,}\) hay\(n\) opciones para el elemento más pequeño. Dado que cada subconjunto de dos elementos debe estar exactamente en uno de estos casos, el número total de dos subconjuntos de elementos es\(1 + 2 + 3 + \cdots + n\text{.}\)

La respuesta 1 y la respuesta 2 son ambas respuestas correctas a la misma pregunta, por lo que deben ser iguales. Por lo tanto,

\ start {ecuación*} 1 + 2 + 3 +\ cdots + n = {n+1\ elige 2}\ final {ecuación*}

\(\square\)

4

Una mujer se va a casar. Tiene 15 mejores amigas pero sólo puede seleccionar 6 de ellas para que sean sus damas de honor, una de las cuales necesita ser su dama de honor. ¿De cuántas maneras puede hacer esto?

1. ¿Y si primero selecciona a las 6 damas de honor, y luego selecciona a una de ellas para que sea la dama de honor?
2. ¿Y si primero selecciona a su dama de honor, y luego a otras 5 doncellas?
3. Explicar por qué\(6 {15 \choose 6} = 15 {14 \choose 5}\text{.}\)

Responder

1. Ella tiene\({15 \choose 6}\) formas de seleccionar a las 6 damas de honor, y luego por cada vía, tiene 6 opciones para la dama de honor. Así tiene\({15 \choose 6}6\) opciones.
2. Ella tiene 15 opciones para quien será su dama de honor. Entonces necesita seleccionar a 5 de los 14 amigos restantes para que sean damas de honor, lo que puede hacer de\({14 \choose 5}\) maneras. Así tiene\(15 {14 \choose 5}\) opciones.
3. Hemos respondido a la pregunta (cuántas fiestas de boda puede elegir la novia) de dos maneras. La primera vía da el lado izquierdo de la identidad y la segunda forma da el lado derecho de la identidad. Por lo tanto, la identidad se mantiene.

5

Dar una prueba combinatoria de la identidad\({n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}\text{.}\)

Responder

Prueba

Pregunta: Tienes un recipiente grande lleno de pelotas de ping-pong, todas con un número diferente en ellas. Debes seleccionar\(k\) de las bolas, poniendo dos de ellas en un frasco y las otras en una caja. ¿De cuántas maneras puedes hacer esto?

Respuesta 1: Primero selecciona 2 de las\(n\) bolas para poner en el frasco. Después selecciona\(k-2\) de las\(n-2\) bolas restantes para poner en la caja. La primera tarea se puede completar de\({n \choose 2}\) diferentes maneras, la segunda tarea en\({n-2 \choose k-2}\) formas. Así hay\({n \choose 2}{n-2 \choose k-2}\) formas de seleccionar las bolas.

Respuesta 2: Primero selecciona\(k\) las bolas del\(n\) en el contenedor. Después recoge 2 de las\(k\) bolas que escogiste para poner en el frasco, colocando el resto\(k-2\) en la caja. La primera tarea se puede completar de\({n \choose k}\) maneras, la segunda tarea en\({k \choose 2}\) formas. Así hay\({n \choose k}{k \choose 2}\) formas de seleccionar las bolas.

Ya que ambas respuestas cuentan lo mismo, deben ser iguales y se establece la identidad.

\(\square\)

6

Considera las cadenas de bits en\(\B^6_2\) (cadenas de bits de longitud 6 y peso 2).

1. ¿Cuántas de esas cadenas de bits empiezan con 1?
2. ¿Cuántas de esas cadenas de bits empiezan con 01?
3. ¿Cuántas de esas cadenas de bits empiezan con 001?
4. ¿Hay alguna otra cadena que aún no hayamos contado? ¿Cuáles y cuántos hay?
5. ¿Cuántas cadenas de bits hay en total en\(\B^6_2\text{?}\)
6. ¿Para qué identidad binomial acaba de dar una prueba combinatoria?

Responder

1. Después del 1, necesitamos encontrar una cadena de 5 bits con uno 1. Hay\({5 \choose 1}\) formas de hacer esto.
2. \({4 \choose 1}\)cuerdas (necesitamos escoger 1 de los 4 slots restantes para ser el segundo 1).
3. \({3 \choose 1}\)cuerdas.
4. Sí. Todavía necesitamos cadenas que comiencen con 0001 (hay\({2 \choose 1}\) de estas) y cadenas que empiecen por 00001 (solo hay\({1 \choose 1} = 1\) de estas).
5. \({6 \choose 2}\)cuerdas
6. Un ejemplo del Teorema del Palo de Hockey:\ begin {equation*} {1\ choose 1} + {2\ choose 1} + {3\ choose 1} + {4\ choose 1} + {5\ choose 1} = {6\ choose 2}\ end {equation*}

7

Contemos cadenas ternarias de dígitos, es decir, cadenas en las que cada dígito puede ser 0, 1 o 2.

1. ¿Cuántas cadenas ternarias de dígitos contienen exactamente\(n\) dígitos?
2. Cuántas cadenas ternarias de dígitos contienen exactamente\(n\) dígitos y\(n\) 2's.
3. Cuántas cadenas ternarias de dígitos contienen exactamente\(n\) dígitos y\(n-1\) 2's. (Pista: ¿dónde puedes poner el dígito que no sea 2 y luego cuál podría ser?)
4. Cuántas cadenas ternarias de dígitos contienen exactamente\(n\) dígitos y\(n-2\) 2. (Pista: ver sugerencia anterior)
5. Cuántas cadenas ternarias de dígitos contienen exactamente\(n\) dígitos y\(n-k\) 2's.
6. Cuántas cadenas ternarias de dígitos contienen exactamente\(n\) dígitos y no 2. (Pista: ¿qué tipo de cadena es esta?)
7. Usa las partes anteriores para dar una prueba combinatoria de la identidad\ begin {ecuación*} {n\ elige 0} + 2 {n\ elige 1} + 2^2 {n\ elige 2} + 2^3 {n\ elige 3} +\ cdots + 2^n {n\ elige n} = 3^n.\ end {equation*}

Responder

1. \(3^n\)cadenas, ya que hay 3 opciones para cada uno de los\(n\) dígitos.
2. \(1\)string, ya que todos los dígitos necesitan ser 2's. Sin embargo, podríamos escribir esto como\({n \choose 0}\) cadenas.
3. Hay\({n \choose 1}\) lugares para poner el dígito no 2. Ese dígito puede ser un 0 o un 1, así que existen\(2{n \choose 1}\) tales cadenas.
4. Debemos elegir dos espacios para llenar con 0 o 1. Hay\({n \choose 2}\) formas de hacerlo. Una vez que se escogen las ranuras, tenemos dos opciones para la primera ranura (0 o 1) y dos opciones para la segunda ranura (0 o 1). Entonces hay un total de\(2^2{n \choose 2}\) tales cadenas.
5. Hay\({n \choose k}\) formas de elegir qué ranuras no tienen los 2's, entonces esas ranuras se pueden llenar de\(2^k\) maneras (0 o 1 para cada ranura). Entonces hay\(2^k{n \choose k}\) tales cadenas.
6. Estas cadenas contienen solo 0's y 1's, por lo que son cadenas de bits. Hay cadenas de\(2^n\) bits. Pero siguiendo el patrón anterior, podríamos escribir esto como\(2^n {n \choose n}\) cadenas.
7. Respondemos a la pregunta de cuántas cadenas de dígitos\(n\) ternarios de longitud hay de dos maneras. Primero, cada dígito puede ser una de tres opciones, por lo que el número total de cadenas es\(3^n\text{.}\) Por otro lado, podríamos dividir la pregunta en casos por cuántos de los dígitos son 2's Si todos son 2's, entonces hay\({n \choose 0}\) cadenas. Si todos menos uno son un 2, entonces hay\(2{n \choose 1}\) cadenas. Si todos menos 2 de los dígitos son 2's, entonces hay\(2^2{n \choose 2}\) cadenas. Elegimos 2 de los\(n\) dígitos para que no sean 2, y luego hay 2 opciones para cada uno de esos dígitos. Y así sucesivamente por cada número posible de 2's en la cadena. Por lo tanto\({n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \)

8

¿Cuántas formas hay de reorganizar las letras en la palabra “reorganizar”? Responda a esta pregunta de al menos dos formas diferentes para establecer una identidad binomial.

Responder

La palabra contiene 9 letras: 3 “r” s, 2 “a” s y 2 “e” s, junto con una “n” y una “g”. Primero podríamos seleccionar las posiciones para las “r” s en\({9 \choose 3}\) formas, luego las “a” s en\({6 \choose 2}\) formas, las “e” s en\({4 \choose 2}\) formas y luego seleccionar uno de los dos puntos restantes para poner la “n” (colocando la “g” en el último lugar). Esto da la respuesta

\ begin {equation*} {9\ choose 3} {6\ choose 2} {4\ choose 2} {2\ choose 1} {1\ choose 1}. \ end {ecuación*}

Alternativamente, podríamos seleccionar las posiciones de las letras en el orden opuesto, lo que daría una respuesta

\ begin {equation*} {9\ choose 1} {8\ choose 1} {7\ choose 2} {5\ choose 2} {3\ choose 3}. \ end {ecuación*}

(donde van las 3 “r” s en los 3 puntos restantes). Estas dos expresiones son iguales:

9

Dar una prueba combinatoria de la identidad\(P(n,k) = {n \choose k}k!\)

Responder

Prueba

Pregunta:\(k\) ¿Cuántas palabras de letras puedes hacer usando letras\(n\) diferentes sin repetir ninguna letra?

Respuesta 1: Hay\(n\) opciones para la primera letra,\(n-1\) opciones para la segunda letra,\(n-2\) opciones para la tercera letra, y así sucesivamente hasta\(n - (k-1)\) elecciones para la letra\(k\) th (ya que\(k-1\) las letras ya se han asignado en ese punto). Se puede escribir el producto de estos números\(\frac{n!}{(n-k)!}\) que es\(P(n,k)\text{.}\) Por lo tanto hay\(P(n,k)\) palabras.

Respuesta 2: Primero elige\(k\) letras para estar en la palabra de las\(n\) elecciones. Esto se puede hacer de\({n \choose k}\) maneras. Ahora arregla esas letras en una palabra. Hay\(k\) opciones para la primera letra,\(k-1\) opciones para la segunda, y así sucesivamente, para un total de\(k!\) arreglos de las\(k\) letras. Así, el número total de palabras es\({n \choose k}k!\text{.}\)

Dado que las dos respuestas son respuestas correctas a una misma pregunta, hemos establecido que\(P(n,k) = {n \choose k}k!\text{.}\)

\(\square\)

10

Establecer la identidad a continuación utilizando una prueba combinatoria.

\ begin {ecuación*} {2\ elige 2} {n\ elige 2} + {3\ elige 2} {n-1\ elige 2} + {4\ elige 2} {n-2\ elige 2} +\ cdots + {n\ elige 2} {2\ elige 2} = {n+3\ elige 5}. \ end {ecuación*}

Responder

Prueba

Pregunta: ¿Cuántos subconjuntos de 5 elementos hay del conjunto?\(\{1,2,\ldots, n+3\}\text{.}\)

Respuesta 1: Elegimos 5 de los\(n+3\) elementos, entonces\({n+3 \choose 5}\) subconjuntos.

Respuesta 2: Dividir esto en casos por lo que es el elemento “medio” (tercer más pequeño) del subconjunto de 5 elementos. El más pequeño que esto podría ser es un 3. En ese caso, tenemos\({2 \choose 2}\) opciones para los números debajo de él, y\({n \choose 2}\) opciones para los números por encima de él. Alternativamente, el número medio podría ser un 4. En este caso hay\({3 \choose 2}\) opciones para los dos números inferiores y\({n-1 \choose 2}\) opciones para los dos números superiores. Si el número medio es 5, entonces hay\({4 \choose 2}\) opciones para los dos números inferiores y\({n-2 \choose 2}\) opciones para los dos números superiores. Y así sucesivamente, todo el camino hasta el mayor el número medio podría ser, que es\(n+1\text{.}\) En ese caso hay\({n \choose 2}\) opciones para los dos números inferiores y\({2 \choose 2}\) opciones para el número superior. Así, el número de 5 subconjuntos de elementos es

\ begin {equation*} {2\ choose 2} {n\ choose 2} + {3\ choose 2} {n-1\ choose 2} + {4\ choose 2} {n-2\ choose 2} +\ cdots + {n\ choose 2} {2\ choose 2}. \ end {ecuación*}

Dado que las dos respuestas responden correctamente a la misma pregunta, tenemos\ begin {equation*} {2\ choose 2} {n\ choose 2} + {3\ choose 2} {n-1\ choose 2} + {4\ choose 2} {n-2\ choose 2} +\ cdots + {n\ choose 2} {2\ choose 2} = {n+3\ choose 5}. \ end {ecuación*}

1.5: Estrellas y barras

1

Un multiset es una colección de objetos, al igual que un conjunto, pero puede contener un objeto más de una vez (el orden de los elementos aún no importa). Por ejemplo,\(\{1,1, 2, 5, 5, 7\}\) es un multiset de tamaño 6.

1. ¿Cuántos juegos de tamaño 5 se pueden hacer usando los 10 dígitos numéricos del 0 al 9?
2. ¿Cuántos conjuntos múltiples de tamaño 5 se pueden hacer usando los 10 dígitos numéricos del 0 al 9?

Responder

1. \({10\choose 5}\)conjuntos. Debemos seleccionar 5 de los 10 dígitos para poner en el conjunto.
2. Usa estrellas y barras: cada estrella representa uno de los 5 elementos del conjunto, cada barra representa un cambio entre dígitos. Entonces hay 5 estrellas y 9 barras, dándonos\({14 \choose 9}\) sets.

2

Cada uno de los problemas de conteo a continuación se puede resolver con estrellas y barras. Para cada uno, di qué resultado el diagrama

\ begin {ecuación*} ***|*||**|\ end {ecuación*}

representa, si hay el número correcto de estrellas y barras para el problema. De lo contrario, diga por qué el diagrama no representa ningún resultado, y cómo sería un diagrama correcto.

1. ¿Cuántas formas hay de seleccionar un puñado de 6 caramelos de un frasco que contiene 5 sabores diferentes?
2. ¿De cuántas formas puedes distribuir 5 piruletas idénticas a 6 niños?
3. ¿Cuántas palabras de 6 letras puedes hacer usando las 5 vocales?
4. Cuántas soluciones hay a la ecuación\(x_1 + x_2 + x_3 + x_4 = 6\text{.}\)

Responder

1. Toma 3 fresas, 1 lima, 0 regaliz, 2 arándanos y 0 chicle.
2. Esto es al revés. No queremos que las estrellas representen a los niños porque los niños no son idénticos, sino que las estrellas sí. En su lugar debemos usar 5 estrellas (para las piruletas) y usar 5 barras para cambiar entre los 6 niños. Por ejemplo,\ begin {equation*} **||***|||\ end {equation*} representaría el resultado con el primer niño recibiendo 2 piruletas, el tercer niño recibiendo 3 y el resto de los niños recibiendo ninguna.
3. Esta es la palabra AAAEOO.
4. Esto no representa una solución. Cada estrella debe representar una de las 6 unidades que suman 6, y las barras deben alternar entre las diferentes variables. Tenemos demasiados bares. Un ejemplo de un diagrama correcto sería\ begin {equation*} *|**||***,\ end {equation*} que representa eso\(x_1 = 1\text{,}\)\(x_2 = 2\text{,}\)\(x_3 = 0\text{,}\) y\(x_4 = 3\text{.}\)

3

Después de la clase de gimnasia tienes la tarea de poner los 14 dodgeballs idénticos en 5 contenedores.

1. ¿De cuántas maneras puedes hacer esto si no hay restricciones?
2. ¿De cuántas maneras puedes hacer esto si cada bin debe contener al menos un dodgeball?

Responder

1. \({18 \choose 4}\)maneras. Cada resultado puede ser representado por una secuencia de 14 estrellas y 4 barras.
2. \({13 \choose 4}\)maneras. Primero pon una bola en cada contenedor. Esto deja 9 estrellas y 4 barras.

4

¿Cuántas soluciones enteras hay para la ecuación\(x + y + z = 8\) para la cual

1. \(x\text{,}\)\(y\text{,}\)y todos\(z\) son positivos?
2. \(x\text{,}\)\(y\text{,}\)y todos\(z\) son no negativos?
3. \(x\text{,}\)\(y\text{,}\)y todos\(z\) son mayores que\(-3\text{.}\)

Responder

1. \({7 \choose 2}\)soluciones. Después de que cada variable obtiene 1 estrella gratis, nos quedan 5 estrellas y 2 barras.
2. \({10 \choose 2}\)soluciones. Tenemos 8 estrellas y 2 barras.
3. \({19 \choose 2}\)soluciones. Este problema equivale a encontrar el número de soluciones a\(x' + y' + z' = 17\) dónde\(x'\text{,}\)\(y'\) y no\(z'\) son negativas. (De hecho, realmente solo hacemos una sustitución. Dejar\(x = x'- 3\text{,}\)\(y = y' - 3\) y\(z = z' - 3\)).

5

Usando los dígitos 2 a 8, encuentre el número de diferentes números de 5 dígitos de tal manera que:

1. Los dígitos no pueden repetirse y deben escribirse en orden creciente. Por ejemplo, 23678 está bien, pero 32678 no lo está.
2. Los dígitos se pueden repetir y deben escribirse en orden no decreciente. Por ejemplo, 24448 está bien, pero 24484 no lo está.

Responder

1. Hay\({7 \choose 5}\) números. Simplemente elegimos cinco de los siete dígitos y una vez elegidos los ponemos en orden creciente.
2. Esto requiere estrellas y barras. Usa una estrella para representar cada uno de los 5 dígitos del número, y usa su posición relativa a las barras para decir qué número llena ese punto. Entonces tendremos 5 estrellas y 6 barras, dando\({11 \choose 6}\) números.

6

Al jugar a Yahtzee, tiras cinco dados regulares de 6 caras. ¿Cuántos resultados diferentes son posibles de un solo rollo? El orden de los dados no importa.

7

Tu amiga te dice que tiene 7 monedas en la mano (solo centavos, monedas de cinco centavos, monedas de diez centavos y cuartos). Si adivinas cuántas de cada tipo de moneda tiene, ella te las dará. Si adivinas al azar, ¿cuál es la probabilidad de que tengas razón?

8

¿Cuántas soluciones enteras\(x_1 + x_2 + x_3 + x_4 = 25\) hay para las cuales\(x_1 \ge 1\text{,}\)\(x_2 \ge 2\text{,}\)\(x_3 \ge 3\) y\(x_4 \ge 4\text{?}\)

9

Resuelve los tres problemas de conteo a continuación. Entonces diga por qué tiene sentido que todos tengan la misma respuesta. Es decir, digamos cómo pueden interpretarlos como los unos a los otros.

1. ¿Cuántas formas hay de distribuir 8 galletas a 3 niños?
2. ¿Cuántas soluciones en números enteros no negativos hay para\(x+y+z = 8\text{?}\)
3. ¿Cuántos paquetes diferentes de 8 crayones puedes hacer usando crayones que vienen en rojo, azul y amarillo?

10

Considerar funciones\(f:\{1,2,3,4,5\} \to \{0,1,2,\ldots,9\}\text{.}\)

1. ¿Cuántas de estas funciones están aumentando estrictamente? Explique. (Una función está aumentando estrictamente si\(a \lt b\text{,}\) entonces\(f(a) \lt f(b)\text{.}\))
2. ¿Cuántas de las funciones son no decrecientes? Explique. (Una función es no decreciente si\(a \lt b\text{,}\) entonces\(f(a) \le f(b)\text{.}\))

11

Cónico, tu autocine de comida rápida con temática matemática favorito ofrece 20 sabores que se pueden agregar a tu refresco. Tienes suficiente dinero para comprar un refresco grande con 4 sabores añadidos. ¿Cuántos brebajes de soda diferentes puedes pedir si:

1. ¿Te niegas a usar alguno de los sabores más de una vez?
2. Rechazas repeticiones pero te preocupas por el orden en que se agreguen los sabores?
3. ¿Te permites múltiples tomas del mismo sabor?
4. Te permites múltiples tomas, y te preocupas por el orden en que se agreguen los sabores?

Responder

1. \({20 \choose 4}\)refrescos (el orden no importa y no se permiten repeticiones).
2. \(P(20, 4) = 20\cdot 19\cdot 18 \cdot 17\)refrescos (no se permiten materias de orden y repeticiones).
3. \({23 \choose 19}\)refrescos (el orden no importa y se permiten repeticiones; 4 estrellas y 19 barras).
4. \(20^4\)refrescos (se permiten materias de orden y repeticiones; 20 opciones 4 veces).

1.6: Recuento avanzado usando PIE

1

El menú del dólar en tu restaurante favorito de comida rápida libre de impuestos tiene 7 artículos. Tienes $10 para gastar. Cuántas comidas diferentes puedes comprar si gastas todo tu dinero y:

1. Compra al menos uno de cada artículo.
2. Posiblemente omita algunos artículos.
3. No obtenga más de 2 de ningún artículo en particular.

Contestar a

\(9 \choose 6\)comidas.

Respuesta b

\(16 \choose 6\)comidas.

Respuesta c

\({16 \choose 6} - \left[{7 \choose 1}{13 \choose 6} - {7 \choose 2}{10 \choose 6} + {7 \choose 3}{7 \choose 6}\right]\)me als. Use PIE para restar todas las comidas en las que obtenga 3 o más de un artículo en particular.

2

Después de una noche de estudios de matemáticas, tú y tus amigos deciden ir a tu restaurante mexicano de comida rápida libre de impuestos favorito, Burrito Chime. Usted decide ordenar fuera del menú del dólar, que tiene 7 artículos. Tu grupo tiene $16 para gastar (y lo gastará todo).

1. ¿Cuántos pedidos diferentes son posibles? Explique. (El orden en el que se realiza el pedido no importa, solo cuál y cuántos de cada artículo que se ordena.)
2. ¿Cuántos pedidos diferentes son posibles si quieres obtener al menos uno de cada artículo? Explique.
3. ¿Cuántos pedidos diferentes son posibles si no obtienes más de 4 de cualquier artículo? Explique.

3

Después de otra clase de gimnasia tienes la tarea de poner los 14 dodgeballs idénticos en 5 contenedores. Esta vez, ninguna papelera puede contener más de 6 bolas. ¿De cuántas maneras puedes limpiar?

Solución

\({18 \choose 4} - \left[ {5 \choose 1}{11 \choose 4} - {5 \choose 2}{4 \choose 4}\right]\text{.}\)Reste todas las distribuciones para las que uno o más contenedores contienen 7 o más bolas.

4

Considera la ecuación Con\(x_1 + x_2 + x_3 + x_4 = 15\text{.}\) cuántas soluciones hay\(2 \le x_i \le 5\) para todos\(i \in \{1,2,3,4\}\text{?}\)

Solución

La forma más fácil de resolver esto es contar las soluciones a\(y_1 + y_2 + y_3 + y_4 = 7\) con\(0 \le y_i \le 3\text{.}\) Al llevar\(x_i = y_i+2\text{,}\) cada solución a esta nueva ecuación corresponde exactamente a una solución a la ecuación original.

Ahora todas las formas de distribuir las 7 unidades a las cuatro\(y_i\) variables se pueden encontrar usando estrellas y barras, específicamente 7 estrellas y 3 barras, así que\({10 \choose 3}\) formas. Pero esto incluye las formas en que a una o más\(y_i\) variables se les puede asignar más de 3 unidades. Así restar, usando PIE. Obtenemos

\ begin {equation*} {10\ choose 3} - {4\ choose 1} {6\ choose 3}. \ end {ecuación*}

El\({4 \choose 1}\) cuenta el número de formas de elegir una variable a sobreasignar, la\({6 \choose 3}\) es el número de formas de asignar las 3 unidades restantes a las 4 variables. Tenga en cuenta que esta es la respuesta final porque no es posible tener dos variables ambas obtienen 4 unidades.

5

Supongamos que planeabas dar 7 estrellas doradas a algunos de los estudiantes de 13 estrellas de tu clase. Cada estudiante puede recibir como máximo una estrella. ¿De cuántas maneras puedes hacer esto? Usa PIE, y también un método más fácil, y compara tus resultados.

6

Con base en la pregunta anterior, dar una prueba combinatoria de la identidad:

\ begin {ecuación*} {n\ elige k} = {n+k-1\ elige k} -\ suma_ {j=1} ^n (-1) ^ {j+1} {n\ elige j} {n+k- (2j+1)\ elige k}. \ end {ecuación*}

7

Ilustrar cómo funciona el conteo de desórdenes escribiendo todas las permutaciones\(\{1,2,3,4\}\) y tachando aquellas que no son desórdenes. Lleva un registro de las permutaciones que tachas más de una vez, usando PIE.

Solución

Los 9 desórdenes son: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.

8

¿Cuántas permutaciones de\(\{1,2,3,4,5\}\) dejar exactamente 1 elemento fijo?

Solución

Primero escoge uno de los cinco elementos a fijar. Para cada una de esas opciones, desmarque las cuatro restantes, usando la fórmula PIE avanzada estándar. Obtenemos\({5 \choose 1}\left( 4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4} 0!\right] \right)\) permutaciones.

9

Diez damas de cierta edad dejan sus sombreros rojos en el chequeo de sombrero de un museo. A medida que se van, el encargado del cheque de sombrero devuelve los sombreros al azar. ¿De cuántas maneras exactamente seis de las damas pueden recibir su propio sombrero (y las otras cuatro no)? Explique.

10

El Grinch se cuela en una habitación con 6 regalos navideños a 6 personas diferentes. Procede a cambiar las etiquetas de nombre en los regalos. ¿De cuántas maneras podría hacer esto si:

1. ¿No se permite ningún presente para terminar con su etiqueta original? Explica lo que representa cada término en tu respuesta.
2. Exactamente 2 regalos mantienen sus etiquetas originales? Explique.
3. Exactamente 5 regalos mantienen sus etiquetas originales? Explique.

11

Considerar funciones\(f: \{1,2,3,4\} \to \{a,b,c,d,e,f\}\text{.}\) ¿Cuántas funciones tienen la propiedad que\(f(1) \ne a\)\(f(2) \ne b\text{,}\) o ambas?

Solución

Hay\(5 \cdot 6^3\) funciones para las cuales\(f(1) \ne a\) y otras\(5 \cdot 6^3\) funciones para las cuales\(f(2) \ne b\text{.}\) Hay\(5^2 \cdot 6^2\) funciones para las cuales ambos\(f(1) \ne a\) y\(f(2) \ne b\text{.}\) Entonces el número total de funciones para las cuales\(f(1) \ne a\)\(f(2) \ne b\) o ambas es

\ begin {ecuación*} 5\ cdot 6^3 + 5\ cdot 6^3 - 5^2\ cdot 6^2 = 1260. \ end {ecuación*}

12

Considerar conjuntos\(A\) y\(B\) con\(|A| = 10\) y\(|B| = 5\text{.}\) ¿Cuántas funciones\(f: A \to B\) son suryectivas?

Solución

\(5^{10} - \left[{5 \choose 1}4^{10} - {5 \choose 2}3^{10} + {5 \choose 3}2^{10} - {5 \choose 4}1^{10}\right]\)funciones. El\(5^{10}\) es todas las funciones de\(A\) a\(B\text{.}\) restamos las que no son suryectivas. Elige uno de los cinco elementos\(B\) para no tener en el rango (en\({5 \choose 1}\) formas) y cuenta todas esas funciones (\(4^{10}\)). Pero esto sobrecuenta las funciones de donde\(B\) se excluyen del rango dos elementos, así que resta esos. Y así sucesivamente, usando PIE.

13

Let\(A = \{1,2,3,4,5\}\text{.}\) ¿Cuántas funciones inyectivas\(f:A \to A\) tienen la propiedad que para cada\(x \in A\text{,}\)\(f(x) \ne x\text{?}\)

14

\(d_n\)Sea el número de descarrilamientos de\(n\) los objetos. Por ejemplo, utilizando las técnicas de esta sección, encontramos

\ begin {ecuación*} d_3 = 3! -\ left ({3\ elige 1} 2! - {3\ elige 2} 1! + {3\ elige 3} 0! \ derecha)\ final {ecuación*}

Podemos usar la fórmula\({n \choose k}\) para escribir todo esto en términos de factoriales. Después de simplificar, pues\(d_3\) obtendríamos

\ begin {ecuación*} d_3 = 3! \ izquierda (1 -\ frac {1} {1} +\ frac {1} {2} -\ frac {1} {6}\ derecha)\ end {ecuación*}

Generaliza esto para encontrar una fórmula más agradable para\(d_n\text{.}\) Bono: Para grandes\(n\text{,}\) aproximadamente ¿qué fracción de todas las permutaciones son desórdenes? Usa tus conocimientos de la serie Taylor a partir del cálculo.