1.2: Enumeración
- Page ID
- 118244
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Muchos problemas básicos en la combinatoria implican contar el número de distribuciones de objetos en celdas, donde podemos o no ser capaces de distinguir entre los objetos y los mismos para las celdas. Además, las celdas pueden estar dispuestas en patrones. Aquí hay ejemplos concretos.
Amanda tiene tres hijos: Dawn, Keesha y Seth.
- Amanda tiene diez billetes de un dólar y decide dar el monto total a sus hijos. ¿De cuántas maneras puede hacer esto? Por ejemplo, una forma en que podría distribuir los fondos es darle a Dawn y Keesha cuatro dólares cada uno con Seth recibiendo el saldo, dos dólares. Otra forma es darle la cantidad total a Keesha, una opción que probablemente no hará muy felices a Dawn y Seth. Tenga en cuenta que oculta dentro de esta pregunta se encuentra la suposición de que Amanda no distingue a los billetes de dólar individuales, digamos examinando cuidadosamente sus números de serie. En cambio, pretendemos que ella solo necesite decidir la cantidad que va a recibir cada uno de los tres hijos.
- Las cantidades de dinero distribuidas a los tres hijos forman una secuencia que si se escribe en orden no creciente tiene la forma:\(a_1, a_2, a_3\) con\(a_1 \geq a_2 \geq a_3 \) y\(a_1 + a_2 + a_3 = 10\). ¿Cuántas secuencias de este tipo hay?
- Supongamos que Amanda decide darle a cada niño por lo menos un dólar. ¿Cómo cambia esto las respuestas a las dos primeras preguntas?
- Ahora supongamos que Amanda tiene diez libros, de hecho los 10 mejores libros de la lista de best-sellers del New York Times, y decide dárselos a sus hijos. ¿De cuántas maneras puede hacer esto? Nuevamente, observamos que hay una suposición oculta —los diez libros son todos diferentes.
- Supongamos que los diez libros están etiquetados\(B_1, B_2, ... , B_{10} \). Los juegos de libros que se dan a los tres hijos son desarticulados por pares y su unión es {\(B_1, B_2, ... , B_{10} \)}. ¿Cuántos conjuntos diferentes de la forma {\(S_1, S_2, S_3 \)} donde\(S_1\)\(S_2\),, y\(S_2\) son disjuntos por pares y\(S_1 \cup S_2 \cup S_3\) = {\(B_1, B_2, ... , B_{10} \)}?
- Supongamos que Amanda decide darle a cada niño al menos un libro. ¿Cómo cambia esto las respuestas a las dos preguntas anteriores?
- ¿Cómo podríamos responder a este tipo de preguntas si diez fueran realmente diez mil (OK, ya no estamos hablando de niños!) y tres eran tres mil? ¿Podrías escribir la respuesta en una sola página en un libro?
Se ensamblará un collar circular con un total de seis cuentas utilizando cuentas de tres colores diferentes. En la Figura 1.1, mostramos cuatro collares de este tipo; sin embargo, tenga en cuenta que los tres primeros son en realidad el mismo collar. Cada una tiene tres cuentas rojas, dos azules y una verde. Por otro lado, el cuarto collar tiene el mismo número de cuentas de cada color pero es un collar diferente.
- ¿Cuántos collares diferentes de seis cuentas se pueden formar usando tres rojos, dos azules y uno verde?
- ¿Cuántos collares diferentes de seis cuentas se pueden formar usando cuentas rojas, azules y verdes (no se tienen que usar todos los colores)?
- ¿Cuántos collares diferentes de seis cuentas se pueden formar usando cuentas rojas, azules y verdes si se tienen que usar los tres colores?
- ¿Cómo podríamos responder a estas preguntas para collares de seis mil cuentas hechas con cuentas de tres mil colores diferentes? ¿Qué software especial se requeriría para encontrar la respuesta exacta y cuánto tiempo tardaría el cómputo?