1.6: Elección con repetición
- Page ID
- 117127
La mayoría de los problemas de permutación y combinación hemos visto elecciones de conteo hechas sin repetición, como cuando preguntamos cuántas tiradas de tres dados hay en las que cada dado tiene un valor diferente. La excepción fue el problema más simple, al pedir el número total de resultados cuando se lanzan dos o tres dados, una simple aplicación del principio de multiplicación. Los problemas típicos de permutación y combinación se pueden interpretar en términos de sacar bolas de una caja, y implícita o explícitamente la regla es que una bola extraída de la caja permanezca fuera de la caja. Si en cambio cada bola se devuelve a la caja después de grabar el sorteo, obtenemos un problema esencialmente idéntico al problema general de los dados. Por ejemplo, si hay seis bolas, numeradas 1—6, y dibujamos tres bolas con reemplazo, el número de posibles resultados es\(6^3\). Otra versión del problema no reemplaza la pelota después de cada empate, sino que permite que múltiples bolas “idénticas” estén en la caja. Por ejemplo, si una caja contiene 18 bolas numeradas 1—6, tres con cada número, entonces los posibles resultados cuando se dibujan tres bolas y no se devuelven a la caja es de nuevo\(6^3\). Sin embargo, si se dibujan cuatro bolas, el problema se vuelve diferente.
Otra forma, quizás más matemática, de formular tales problemas es introducir la idea de un multiset. Un multiset es como un conjunto, excepto que los elementos pueden aparecer más de una vez. Si\(\{a,b\}\) y\(\{b,c\}\) son conjuntos ordinarios, decimos que la unión\(\{a,b\}\cup\{b,c\}\) es\(\{a,b,c\}\), no\(\{a,b,b,c\}\). Si los interpretamos como multiconjuntos, sin embargo, sí escribimos\(\{a,b,b,c\}\) y consideramos que esto es diferente a\(\{a,b,c\}\). Para distinguir multiconjuntos de conjuntos, y para acortar la expresión en la mayoría de los casos, usamos un número de repetición con cada elemento. Por ejemplo, escribiremos\(\{a,b,b,c\}\) como\(\{1\cdot a,2\cdot b,1\cdot c\}\). Al escribir\(\{1\cdot a,1\cdot b,1\cdot c\}\) enfatizamos que se trata de un multiset, aunque ningún elemento aparezca más de una vez. También permitimos incluir elementos un número infinito de veces, indicado con\(\infty\) para el número de repetición, como\(\{\infty\cdot a, 5\cdot b, 3\cdot c\}\).
Generalmente hablando, los problemas en los que los números de repetición son infinitos son más fáciles que aquellos que involucran números de repetición finitos. Dado un multiset\(A=\{\infty\cdot a_1,\infty\cdot a_2,\ldots,\infty\cdot a_n\}\), ¿cuántas permutaciones de los elementos de longitud\(k\) hay? Es decir, ¿cuántas secuencias se\(x_1,x_2,\ldots,x_k\) pueden formar? Esto es fácil: la respuesta es\(n^k\).
Ahora considere combinaciones de un multiconjunto, es decir, submulticonjuntos: Dado un multiconjunto, ¿cuántos submulticonjuntos de un tamaño dado tiene? Decimos que un multiconjunto\(A\) es un submulticonjunto de\(B\) si el número de repetición de cada elemento de\(A\) es menor o igual a su número de repetición en\(B\). Por ejemplo,\(\{20\cdot a, 5\cdot b, 1\cdot c\}\) es un submulticonjunto de\(\{\infty\cdot a, 5\cdot b, 3\cdot c\}\). Un multiconjunto es finito si contiene solo un número finito de elementos distintos, y los números de repetición son todos finitos. Supongamos otra vez eso\(A=\{\infty\cdot a_1,\infty\cdot a_2,\ldots,\infty\cdot a_n\}\); ¿cuántos submulticonjuntos finitos tiene de tamaño\(k\)? Esto al principio parece bastante difícil, pero puesto en la forma adecuada resulta ser un problema familiar. Imagina que tenemos\(k+n-1\) “espacios en blanco”, así:
\[\underline{\qquad}\quad \underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\cdots\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\nonumber\]
Ahora colocamos\(n-1\) marcadores en algunos de estos spots:
\[\underline{\wedge}\quad \underline{\qquad}\quad\underline{\wedge}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\wedge}\quad\underline{\qquad}\quad\cdots\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\wedge}\quad\underline{\qquad}\nonumber\]
Esto identifica de manera única un submulticonjunto: llena todos los espacios en blanco hasta el primero\(\land\) con\(a_1\), hasta el segundo con\(a_2\), y así sucesivamente:
\[\underline{\wedge}\quad \underline{a_2}\quad\underline{\wedge}\quad\underline{a_3}\quad\underline{a_3}\quad\underline{a_3}\quad\underline{\wedge}\quad\underline{a_4}\quad\cdots\quad\underline{a_{n-1}}\quad\underline{a_{n-1}}\quad\underline{\wedge}\quad\underline{a_n}\nonumber\]
Entonces este patrón corresponde al multiset\(\{1\cdot a_2,3\cdot a_3,\ldots, 1\cdot a_n\}\). Rellenar los marcadores\(\land\) de todas las formas posibles produce todos los submulticonjuntos posibles de tamaño\(k\), por lo que existen\(k+n-1\choose n-1\) tales submulticonjuntos. Tenga en cuenta que esto es lo mismo que\(k+n-1\choose k\); la parte difícil en la práctica es recordar que el\(-1\) va con el\(n\), no con el\(k\).
\[\bullet\quad\bullet\quad\bullet\nonumber\]
Resumiendo los puntos altos hasta el momento: El número de permutaciones de\(n\) cosas tomadas\(k\) a la vez sin reemplazo es\( P(n,k)=n!/(n-k)!\); el número de permutaciones de\(n\) cosas tomadas\(k\) a la vez con reemplazo es\( n^k\). El número de combinaciones de\(n\) cosas tomadas\(k\) a la vez sin reemplazo es\({n\choose k}\); el número de combinaciones de\(n\) cosas tomadas\(k\) a la vez con reemplazo es\({k+n-1 \choose k}\).
\[\bullet\quad\bullet\quad\bullet\nonumber\]
Si\(A=\{m_1\cdot a_1, m_2\cdot a_2,\ldots,m_n\cdot a_n\}\), preguntas similares pueden ser bastante duras. Aquí hay un caso especial más fácil: ¿Cuántas permutaciones del multiset\(A\) hay? Es decir, ¿cuántas secuencias consisten en\(m_1\) copias de\(a_1\),\(m_1\) copias de\(a_2\), etc.? Este problema sucumbe al exceso: supongamos para empezar que podemos distinguir entre los diferentes ejemplares de cada uno\(a_i\); podrían ser coloreados de manera diferente por ejemplo: un rojo\(a_1\), un azul\(a_1\), y así sucesivamente. Entonces tenemos un conjunto ordinario con\(M=\sum_{i=1}^n m_i\) elementos y\(M!\) permutaciones. Ahora bien, si ignoramos los colores, para que todas las copias de\(a_i\) luzcan igual, nos encontramos con que hemos sobrecontado las permutaciones deseadas. Las permutaciones con, digamos, los\(a_1\) artículos en las mismas posiciones se ven todos iguales una vez que ignoramos los colores de la\(a_1\) s. ¿Cuántas de las permutaciones originales tienen esta propiedad? \(m_1!\)las permutaciones aparecerán idénticas una vez que ignoremos los colores de los\(a_1\) artículos, ya que hay\(m_1!\) permutaciones de los\(a_1\) s coloreados en\(m_1\) posiciones dadas. Entonces después de tirar duplicados, el número de permutaciones restantes es\(M!/m_1!\) (asumiendo que\(a_i\) las otras siguen siendo distinguibles). Entonces el mismo argumento se aplica a la\(a_2\) s: hay\(m_2!\) copias de cada permutación una vez que ignoramos los colores de la\(a_2\) s, por lo que hay\( {M!\over m_1!\,m_2!}\) distintas permutaciones. Continuando de esta manera, vemos que el número de permutaciones distintas una vez que se ignoran todos los colores es\[\frac{M!}{ m_1!\,m_2!\cdots m_n!}.\nonumber\]
Esto se escribe frecuentemente\[{M\choose m_1\;\;m_2\;\ldots\; m_n},\nonumber\] llamado coeficiente multinomial. Aquí la segunda fila tiene entradas\(n\) separadas, no una sola entrada de producto. Tenga en cuenta que si\(n=2\) esto es\[\label{eq:1}\eqalignno{ {M\choose m1\;\;m2}&= {M!\over m_1!\,m_2!}={M!\over m_1!\,(M-m_1)!}={M\choose m_1}.}\nonumber\]
Esto es fácil de ver combinatorialmente: dado\(\{m_1\cdot a_1, m_2\cdot a_2\}\) podemos formar una permutación eligiendo los\(m_1\) lugares que ocuparán\(a_1\), llenando los\(m_2\) lugares restantes con\(a_2\). El número de permutaciones es el número de formas de elegir las\(m_1\) ubicaciones, que es\(M\choose m_1\).
Ejemplo\(\PageIndex{1}\)
¿Cuántas soluciones\( x_1+x_2+x_3+x_4=20\) tiene en enteros no negativos? Es decir, ¿cuántas 4-tuplas\((m_1,m_2,m_3,m_4)\) de enteros no negativos son soluciones a la ecuación?
Solución
En realidad hemos resuelto este problema: ¿Cuántos submulticonjuntos de tamaño 20 hay del multiset\(\{\infty\cdot a_1,\infty\cdot a_2,\infty\cdot a_3,\infty\cdot a_4\}\)? Un submulticonjunto de tamaño 20 es de la forma\(\{m_1\cdot a_1,m_2\cdot a_2,m_3\cdot a_3,m_4\cdot a_4\}\) donde\(\sum m_i=20\), y estos están en 1—1 correspondencia con el conjunto de 4-tuplas\((m_1,m_2,m_3,m_4)\) de enteros no negativos tales que\(\sum m_i=20\). Así, el número de soluciones es\(20+4-1\choose 20\). Este razonamiento se aplica en general: el número de soluciones a\[\sum_{i=1}^n x_i = k\nonumber\] es\[{k+n-1\choose k}.\nonumber\]
Esto inmediatamente sugiere algunas generalizaciones: en lugar del número total de soluciones, podríamos querer el número de soluciones con las variables\(x_i\) en ciertos rangos, es decir, podríamos requerir que\(m_i\le x_i\le M_i\) para algunos límites inferior y superior\(m_i\) y\(M_i\).
Los límites superiores finitos pueden ser difíciles de tratar; si lo requerimos\(0\le x_i\le M_i\), esto es lo mismo que contar los submulticonjuntos de\(\{M_1\cdot a_1,M_2\cdot a_2,\ldots,M_n\cdot a_n\}\). Los límites inferiores son más fáciles de tratar.
Ejemplo\(\PageIndex{2}\)
Encuentre el número de soluciones para\( x_1+x_2+x_3+x_4=20\) con\(x_1\ge 0\),\(x_2\ge 1\),\(x_3\ge 2\),\(x_4\ge -1\).
Solución
Podemos transformar esto en el problema inicial en el que todos los límites inferiores son 0. Las soluciones que buscamos contar son las soluciones de esta ecuación alterada:\[ x_1+(x_2-1)+(x_3-2)+(x_4+1)=18.\nonumber\] Si establecemos\(y_1=x_1\),\(y_2=x_2-1\),\(y_3=x_3-2\), y\(y_4=x_4+1\), entonces\((x_1,x_2,x_3,x_4)\) es una solución a esta ecuación si y solo si\((y_1,y_2,y_3,y_4)\) es una solución a\[ y_1+y_2+y_3+y_4=18,\nonumber\] y además los límites en el\(x_i\) están satisfechos si y sólo si\(y_i\ge 0\). Dado que el número de soluciones a la última ecuación es\(18+4-1\choose 18\), este es también el número de soluciones a la ecuación original.