5.2: Ordenar un conjunto que contiene repetición

En el apartado anterior, el nuevo trabajo provino de mirar combinaciones donde se permite la repetición o el reemplazo. Para nuestros propósitos, asumimos que la repetición o sustitución era efectivamente ilimitada; es decir, la tienda solo podría tener bagels de\(30\) canela y pasas, pero como Chris solo estaba ordenando cuatro bagels, ese límite no importaba.

En esta sección, vamos a considerar la situación en la que hay un número fijo de objetos en total; algunos de ellos son “repetidos” (es decir, indistinguibles entre sí), y queremos determinar de cuántas formas se pueden organizar (permutar). Esto puede surgir en una variedad de situaciones.

Ejemplo\(\PageIndex{1}\)

Cuando Chris regresa de la tienda de donas, descubre que Mohammed, Jing, Karl y Sara se han unido a la sesión de estudio. Ha comprado dos donas de chocolate, tres donas de arce y tres donas de crema Boston. ¿De cuántas maneras se pueden distribuir las donas para que todos reciban una dona?

Solución

Inicialmente, esto se parece mucho a una pregunta de permutación: necesitamos averiguar la cantidad de formas de organizar las donas en algún orden, y darle la primera rosca al primer alumno, la segunda rosca al segundo estudiante, y así sucesivamente.

La nueva pieza clave en este problema es que, a diferencia de las permutaciones que hemos estudiado hasta ahora, las dos donas de chocolate son indistinguibles (al igual que las tres donas de arce y las tres donas de crema Boston). Esto quiere decir que no hay diferencia entre darle la primera rosilla de chocolate a Tom y la segunda a Mohammed, y darle la primera dona de chocolate a Mohammed y la segunda a Tom.

Una forma de resolver este problema es mirarlo como una serie de combinaciones de las personas, más que como una pregunta de permutación sobre las donas. En lugar de arreglar las donas, primero podemos elegir cuáles dos de las ocho personas recibirán las dos donas de chocolate. Una vez hecho eso, de las seis personas restantes, elegimos cuáles tres recibirán donas de arce. Por último, las tres personas restantes reciben donas de crema Boston. Así, la solución es\(\binom{8}{2} \binom{6}{3}\).

Otro enfoque es más parecido al enfoque que usamos para averiguar cuántas\(r\) combinaciones hay de\(n\) objetos. En este enfoque, comenzamos por señalar que podríamos arreglar las ocho donas en\(8!\) órdenes si todas fueran distintas. Para cualquier elección fija de dos personas que reciben las donas de chocolate, hay\(2!\) formas en las que esas dos donas de chocolate podrían haberse distribuido a ellas, por lo que en\(8!\) los pedidos de las donas, se ha contado cada una de estas opciones para quien obtiene las donas de chocolate\(2!\) veces en lugar de una vez. De igual manera, para cualquier elección fija de tres personas que reciben las donas de arce, hay\(3!\) formas en que estas tres donas de arce podrían haberse distribuido a ellas, y cada una de estas elecciones se ha contado\(3!\) veces en lugar de una vez. Lo mismo es cierto para las tres donas de crema Boston. Así, la solución es\(\dfrac{8!}{(2!3!3!)}\).

Desde:

\(\binom{8}{2} \binom{6}{3} = \dfrac{8!}{2!6!} \cdot \dfrac{6!}{3!3!} = \dfrac{8!}{(2!3!3!)} \)

vemos que estas soluciones son de hecho idénticas aunque se ven diferentes.

Esta técnica puede ser utilizada para darnos una fórmula general para contar el número de formas de ordenar\(n\) objetos algunos de los cuales son indistinguibles entre sí.

Teorema\(\PageIndex{1}\)

Supongamos que:

• hay\(n\) objetos;
• para cada uno\(i\) con\(1 ≤ i ≤ m\),\(r_i\) de ellos son de tipo\(i\) (indistinguibles entre sí); y
• \(r_1 + . . . + r_m = n\).

Entonces el número de arreglos (permutaciones) de estos\(n\) objetos es

\[\dfrac{n!}{r_1!r_2!...r_m!}\]

Prueba

Utilizamos la misma idea que en la solución al Ejemplo 5.2.1, anterior. Cualquiera de los dos enfoques funcionará, pero usaremos el primero. Habrá\(n\) posiciones en el orden final de los objetos. Comenzamos por elegir\(r_1\) de estos para sostener los objetos de tipo\(1\). Entonces elegimos\(r_2\) de ellos para sostener los objetos de tipo\(2\), y así sucesivamente. En última instancia, elegimos\(r_m\) las ubicaciones finales (de manera\(\binom{r_m}{r_m} = 1\) posible) para contener los objetos de tipo\(m\).

Usando la regla del producto, el número total de arreglos es:

\[ \begin{equation} \begin{split} &= \binom{n}{r_1} \binom{n - r_1}{r_2} ... \binom{n - r_1 - ... - r_{m-1}}{r_m} \\ &= \dfrac{n!}{r_1!(n-r_1)!} \cdot \dfrac{(n-r_1)!}{r_2!(n-r_1-r_2)!} \cdot ... \cdot \dfrac{(n-r_1-...-r_{m-1})!}{r_m!0!} \\ &= \dfrac{n!}{r_1!r_2!...r_m!} \end{split} \end{equation} \]

ya que todos los demás términos cancelan.

Tenemos notación para este valor también.

Nota

Usamos\(\binom{n}{r_1,...,r_m}\) para denotar el número de arreglos de\(n = r_1 + . . . + r_m\) objetos donde para cada uno\(i\) con\(1 ≤ i ≤ m\) tenemos objetos\(r_i\) indistinguibles de tipo\(i\). Por lo tanto,

\[\binom{n}{r_1,...,r_m} = \dfrac{n!}{r_1!...r_m!}\]

Esto a veces puede aplicarse de formas inesperadas.

Ejemplo\(\PageIndex{2}\)

Cathy, Akos y Dagmar irán a un aula de\(30\) alumnos. Cada uno de ellos sacará a cuatro estudiantes para trabajar con ellos en un entorno de grupos pequeños. ¿De cuántas maneras se pueden elegir los grupos?

Solución

A pesar de que todos los alumnos de la clase son distintos, el orden en que son elegidos para el grupo en el que terminan no importa. Una forma de hacer la selección sería poner los nombres Cathy, Akos y Dagmar en un sombrero (cuatro veces cada uno) junto con\(18\) hojas de papel en blanco. Cada alumno podría elegir una hoja de papel y se le asignaría al grupo correspondiente al nombre que eligiera. Los cuatro resbalones con el nombre de Cathy en ellos son idénticos, al igual que los cuatro con el nombre de Akos, los cuatro con el nombre de Dagmar y los resbalones\(18\) en blanco.

Así, la solución a este problema es

\(\binom{30}{4,4,4,18} = \dfrac{30!}{(4!4!4!18)} \)

También podríamos resolver esto de manera más directa, permitiendo que cada una de Cathy, Akos y Dagmar elija cuatro estudiantes; la elección de Cathy se puede hacer de\(\binom{30}{4}\) maneras; luego Akos' en\(\binom{26}{4}\) formas; luego la de Dagmar en\(\binom{22}{4}\) formas, y el producto de estas es\(\dfrac{30!}{(4!4!4!18)}\).

Ejercicio\(\PageIndex{1}\)

Evaluar los siguientes problemas.

1. El maestro de Charlie le da un conjunto de palabras magnéticas. Tiene que hacer un “poema” usando todos ellos. Las palabras son: on, the, one, up, a, tree, the, child, on, salta, siente, the, child, with. ¿Cuántos “poemas” diferentes puede crear Charlie, si algún orden de las palabras se considera un poema?
2. Al llenar la orden de recaudación de fondos del equipo de fútbol, la compañía de chocolate envió seis cajas extra de almendras cubiertas de chocolate, tres cajas adicionales de mentas y dos cajas adicionales de chocolate simple. ¿De cuántas formas se pueden distribuir equitativamente los extras a las once familias que ordenaron chocolates?

Ejercicio\(\PageIndex{2}\)

Demostrar el Teorema Multinomial: que

\((x_1 + x_2 + · · · + x_m) = \sum_{k_1 + k_2 + · · · + k_m} \binom{n}{k_1, k_2, . . . , k_m} \prod_{1≤r≤m} x_r^{k_r} \)

[Pista: Elija valores arbitrarios para\(k_1, k_2, . . . , k_m\) tal que

\(k_1 + k_2 + · · · + k_m\)

y evaluar el coeficiente de\(x_1^{k_1}x_2^{k_2}...x_m^{k_m}\) que proviene del producto en el lado izquierdo de la ecuación.