Permutaciones de 6 letras en MISSISSIPPI

Question

¿Cuántas permutaciones de 6 letras se pueden formar usando solo las letras de la palabra, MISSISSIPPI? Entiendo el caso trivial donde no hay letras repetidas en la palabra (para organizar palabras más pequeñas) pero me tropiezo cuando esto no se cumple. Me pregunto si hay una forma más sencilla de calcular todas las posibles permutaciones, como alternativa a calcular manualmente todas las posibles combinaciones de 6 letras y sumando las permutaciones correspondientes de cada una. Además, ¿existe un método para generalizar el resultado basado en cualquier número P de letras en un conjunto con letras repetidas, para calcular el número de permutaciones de n-letras?

Disculpa si esta pregunta (o similar) ya ha sido formulada anteriormente, pero si es así, por favor enlázame a la página relevante. También pido disculpas si la explicación no está clara, o si he utilizado incorrectamente algún término (soy solo un estudiante de secundaria). Si es así, por favor comenta. :-)

Answer 1

Puedo pensar en un enfoque de tipo función generadora. Tienes 1 M, 2 P's, 4 I's y 4 S's en la palabra MISSISSIPPI. Supongamos que seleccionaste los dos P's y cuatro I's, el número de permutaciones sería $\frac{6!}{4! 2!}$. Sin embargo, necesitamos sumar sobre todas las posibles selecciones de 6 letras de este grupo.

La respuesta será el coeficiente de $x^6$ en

$$\begin{equation} 6!\left(1 + \frac{x}{1!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right)^2 \end{equation}$$

Cada término polinómico corresponde a las formas en que podrías hacer una selección de una letra dada. Así que tienes $1 + x$ para la letra M y $1 + x + x^2/2$ para las 2 letras P y así sucesivamente.

El coeficiente de $x^6$ resulta ser 1610 en este caso.

EDICIÓN: (Estoy ampliando un poco en respuesta al comentario de George).

Este es un enfoque bastante estándar para este tipo de problemas de conteo. El valor de $x$ no es relevante para el problema en absoluto. El beneficio de usar tales polinomios es que te da una herramienta agradable para resolver el problema "mecánicamente". La idea es que al observar el coeficiente de un término particular en el polinomio expandido, obtienes la respuesta.

Cuando escribí un término (1+x) correspondiente a la letra M, captura dos posibilidades

1) Podría excluir M (lo que corresponde al coeficiente de x^0 que es 1)

2) Podría incluir M, lo que corresponde al coeficiente de x^1 que es uno.

Supongamos seleccionas 1M, 2I's, 2P's y 1 S. Esto se codifica mediante el término $x^1\cdot x^2 \cdot x^2 \cdot x^1$. El primer término de $x^1$ corresponde a seleccionar la única M. El primer término de $x^2$ corresponde a seleccionar 2 I's (que son idénticos). Usando una lógica similar, el siguiente $x^2$ es para 2P's y el último $x^1$ es para 1S. Dado que estás interesado en permutaciones con repetición, el número de permutaciones para este caso será $\frac{6!}{2!2!}$, que debería ser el coeficiente de este término.

¿Cómo codificarías 0 M, 3I's, 2P's y 1S? El término sería entonces $x^0 \cdot x^3 \cdot x^2 \cdot x^1$. Sin embargo, este término tendría que multiplicarse por $\frac{6!}{3!2!}$ para mantener el conteo correcto. El $6!$ en el numerador será común a todos esos términos. El denominador depende de tu selección de letras.

Necesitas sumar todas esas posibilidades. En lugar de enumerarlas todas, lo cual sería laborioso, representas la posibilidad de elegir cada letra por un polinomio. Como ejemplo, para 4 S's. tienes $1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}$. Divides $x^n$ por $n!$ para mantener el conteo correcto.

Luego multiplicas los polinomios y miras el coeficiente apropiado.

$$\begin{equation} 6!\left(1 + \frac{x}{1!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right)^2 \end{equation}$$

Expande este polinomio y mira el coeficiente de $x^6$ que te da la respuesta.

Para usos más potentes de este tipo de enfoque, por favor lee el libro en http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf (Advertencia - es un archivo PDF grande).

Answer 2

Agregaré un enfoque "básico" para complementar la excelente solución de la función generadora dada por @svenkatr anteriormente.

La dificultad radica en las letras repetidas; obtener el número de permutaciones de 6 letras de $ABCDEFGHIJK$ es simplemente el factorial descendente $(11)_6 = 332640$. Sin embargo, tomar $6$ letras del multiconjunto $\{M, I^4, S^4,P^2\}$ significa que las combinaciones son mucho menores, ya que las repeticiones son inevitables (solo hay $4$ letras diferentes) y pueden tener una multiplicidad bastante alta.

Para un determinado patrón de repetición no ordenado en las 6 letras elegidas, digamos $aaaabc$, podemos completar esto a partir de la elección de letras basada en qué letras ocurren en una multiplicidad adecuada. Para el ejemplo $aaaabc$, $a$ puede ser o bien $I$ o $S$ mientras que luego $b$ y $c$ son una elección libre de las letras restantes, $\binom 32 = 3$ dando $6$ opciones para completar este patrón. Luego, las disposiciones de este patrón son el trinomio $\binom {6}{4,1,1} = 30$.

Entonces, una vez que identifiquemos todos los patrones, podemos evaluar cada uno a su vez para obtener una respuesta total: $$\begin{array}{|c|c|} \hline \text{Para este patrón:} & \text{opciones para completar} & \text{disposiciones} & \text{opciones totales} \\[1ex] \hline aaaabb & \binom 21 \binom 21 = 4 & \binom{6}{4,2} = 15 & 60 \\[1ex] aaaabc & \binom 21 \binom 32 = 6 & \binom{6}{4,1,1} = 30 & 180 \\[1ex] aaabbb & \binom 22 = 1 & \binom{6}{3,3} = 20 & 20 \\[1ex] aaabbc & \binom 21 \binom 21 \binom 21 = 8 & \binom{6}{3,2,1} = 60 & 480 \\[1ex] aaabcd & \binom 21 \cdot \binom 33 = 2 & \binom{6}{3,1,1,1} = 120 & 240 \\[1ex] aabbcc & \binom 33 = 1 & \binom{6}{2,2,2} = 90 & 90 \\[1ex] aabbcd & \binom 32\cdot \binom 22 = 3 & \binom{6}{2,2,1,1} = 180 & 540 \\[1ex] \hline \end{array}$$

sumando un total de $\fbox{1610}$ opciones en general.