n!/(n₁!n₂!...nₖ!) para conjuntos con elementos repetidos.
Las permutaciones de multiconjuntos tratan sobre la cantidad de formas en que puedes acomodar una colección de objetos en una fila cuando algunos de los objetos son idénticos (indistinguibles). A diferencia de las permutaciones estándar donde cada elemento es único (lo que da $n!$ arreglos), un multiconjunto tiene elementos repetidos. Si cambiaras de lugar dos elementos idénticos, el arreglo se vería exactamente igual. Por eso, si solo calculas $n!$, vas a estar contando de más.
Para encontrar el número correcto de permutaciones distintas, tienes que aplicar un factor de corrección al conteo factorial estándar. La intuición viene de la "regla de la división" del conteo. Primero haces de cuenta que todos los objetos son distintos para obtener un conteo total, y luego divides entre el número de formas en que los objetos idénticos pueden cambiar de lugar entre sí. Como el orden interno de los objetos idénticos no genera una secuencia nueva que puedas distinguir, divides para quitar esas redundancias.
Este concepto es fundamental en la combinatoria y aparece seguido en competencias como el AMC 10 y 12. Un ejemplo muy famoso son los problemas de "ordenar palabras" (por ejemplo, contar los anagramas de "MISSISSIPPI"). Más allá de solo contar, esta técnica es la base del Teorema Multinomial y es esencial para calcular probabilidades en situaciones con estados repetidos.
Imagina que $S$ es un multiconjunto con $n$ objetos de $k$ tipos distintos. Sean $n_1, n_2, \dots, n_k$ las cantidades de cada tipo de objeto, de modo que: $$ n = n_1 + n_2 + \dots + n_k $$
El número de permutaciones distintas (arreglos lineales) del multiconjunto $S$ lo calculas con el coeficiente multinomial: $$ P(n; n_1, n_2, \dots, n_k) = \frac{n!}{n_1! n_2! \dots n_k!} $$
Formulación Alternativa (Producto de Combinaciones): Este valor es equivalente a ir eligiendo las posiciones para cada tipo de objeto una tras otra: $$ \binom{n}{n_1} \binom{n-n_1}{n_2} \binom{n-n_1-n_2}{n_3} \dots \binom{n_k}{n_k} $$
Teorema: El número de permutaciones distintas de $n$ objetos, donde hay $n_1$ objetos indistinguibles del tipo 1, $n_2$ objetos indistinguibles del tipo 2, ..., y $n_k$ objetos indistinguibles del tipo $k$, es $\frac{n!}{n_1!n_2!\dots n_k!}$.
Demostración: Aquí la idea es usar el método de sobreconteo (corrigiendo por la falta de distinción).
Paso 1: Distingue todos los elementos Supón que por un momento les pones etiquetas a los elementos idénticos para que sean distintos. Por ejemplo, si tienes $n_1$ objetos del tipo $A$, los etiquetas como $A_1, A_2, \dots, A_{n_1}$. Haz esto para los $k$ tipos. Ahora tienes un conjunto de $n$ objetos distintos. El número de formas de acomodar $n$ objetos distintos es simplemente: $$ N_{\text{distinct}} = n! $$
Paso 2: Analiza el sobreconteo Considera cualquier arreglo específico del multiconjunto (donde no distingues los objetos idénticos). Cuando pusiste las etiquetas en el Paso 1, este mismo arreglo generó muchas versiones "distintas" con etiquetas.
Como el acomodo de los objetos de un tipo es independiente del acomodo de los de otro tipo, el número total de permutaciones con etiquetas que corresponden a una sola permutación sin etiquetas es el producto: $$ R = n_1! \times n_2! \times \dots \times n_k! $$
Paso 3: Aplica la Regla de la División Sea $X$ el número real de permutaciones distintas del multiconjunto. Como cada permutación válida corresponde exactamente a $R$ permutaciones con etiquetas del Paso 1, tienes que: $$ X \cdot R = N_{\text{distinct}} $$ $$ X \cdot (n_1! n_2! \dots n_k!) = n! $$
Si despejas $X$: $$ X = \frac{n!}{n_1! n_2! \dots n_k!} $$
$\square$