MISSISSIPPI con 2 limitaciones

Question

Este es un post con dos preguntas:

El problema se plantea:

¿Cuántos arreglos de MISSISSIPPI hay en los que la primera I precede a la primera S y la primera S precede a la primera P?

Primera respuesta y pregunta:

Para el $S$ la construcción básica es:

$$ I \wedge S \wedge P \wedge P \wedge, $$

así que hay 4 espacios donde poner 3 $S$ 's: $\binom{6}{3}$ .

Para cada disposición del $S$ 's hay $8$ espacios donde encajar $3$ $I$ 's: $\binom{10}{3}$ .

Por último, para el $M$ Hay 11 maneras de decirlo. Respuesta: $\binom{6}{3}\binom{10}{3}\binom{11}{1}=26400$ . Aparentemente, esto está mal, ¿no?

---

Segunda respuesta y pregunta

La construcción básica es

$$ \wedge I \wedge S \wedge P \wedge P \wedge, $$

pero aquí, las eses pueden ocupar lugares $2-5$ , $I$ y la M puede ocupar todas las plazas.

(a) Hay cero $I$ 's en lugares $2-5$ y $M$ también está en su lugar $1$ : $1 \binom{6}{3}\frac{4!}{3!}$ . (La primera es arreglar el $S$ 's, los arreglan en los lugares permitidos, y el último término es arreglar $I$ 's y el $M$ en primer lugar.

(b) Hay cero $I$ 's en lugares $2-5$ y $M$ también está en lugares $2-5$ : $\frac{4!}{3!} \binom{7}{4} 1$ . (Una vez más, el primer término es ordenar el $S$ 's y el $M$ y luego colocarlos en los lugares $2-5$ el último término es la disposición de $3$ idénticas I's.

(c) $1$ $I$ en lugares $2-5$ y $M$ en su lugar $1$ : $\frac{4!}{3!}\binom{7}{4}\frac{3!}{2!}$

(d) $1$ $I$ en lugares $2-5$ y $M$ en lugares $2-5$ : $\frac{5!}{3!}\binom{8}{5} 1$

(e) $2$ $I$ 's en lugares $2-5$ y $M$ en su lugar $1$ : $\frac{5!}{3!2!}\binom{8}{5} 2!$

(f) $2$ $I$ 's en lugares $2-5$ y $M$ en lugares $2-5$ : $\frac{6!}{3!2!}\binom{9}{6}$

(g) $3$ $I$ 's en lugares $2-5$ y $M$ en su lugar $1$ : $\frac{6!}{3!3!}\binom{9}{6}$

(h) $3$ $I$ 's en lugares $2-5$ y $M$ en lugares $2-5$ : $\frac{7!}{3!3!}\binom{10}{7}$

Sumando todos los casos obtengo el mismo número que mi respuesta 1: $\binom{6}{3}\binom{10}{3}\binom{11}{1}$ .

Ahora, mi segunda pregunta es la siguiente, ¿está mal este último argumento? No sé si puedo guardar mi respuesta porque por ejemplo creo que tengo doble conteo en el siguiente ejemplo (puse entre paréntesis la posición de las letras que ocupan un espacio permitido):

$$ (M) I (SISI) S \wedge P (IS) P \wedge = \\ (M) I \wedge S (ISIS) P (IS) P \wedge $$

Este es un caso especial de (g), y cuentan de manera diferente debido a la posición de las letras y la permutación en la disposición, pero ambos están al final la palabra $MISISISPISP$ .

Answer 1

Respuesta a la primera pregunta. Su método es básicamente correcto. Sin embargo, después de haber $$I\cdots S\cdots P\cdots P\cdots\ ,$$ hay tres posibles lugares para el resto de $S$ s, no cuatro, porque el que ya tiene es el primero $S$ . Del mismo modo, cuando se tiene $$I\cdots S\cdots S\cdots P\cdots P\cdots S\cdots S\cdots$$ o algo similar, hay siete plazas, no ocho, para el resto $I$ s. Así que el número de arreglos es $$\binom53\binom9311=9240\ .$$

Nota que para contar correctamente los arreglos hay que especificar al principio cuál es el primero $S$ (y $I$ y $P$ ). Una vez hecho esto, obviamente no se puede colocar otro $S$ antes de la primera $S$ . Si no lo haces así, entonces tomando por ejemplo $$I\cdots_1S\cdots_2$$ y poniendo el siguiente $S$ en su lugar $1$ o lugar $2$ le dará el mismo arreglo contado dos veces.

Answer 2

He aquí una solución alternativa:

Dado que hay $11$ cartas en MISSISSIPPI, hay $11$ maneras de colocar la M. Debemos llenar el resto $10$ posiciones con cuatro I, cuatro S y dos P. Como la primera I debe aparecer antes de la primera S y la primera S debe aparecer antes de la primera P, debemos llenar la posición abierta más a la izquierda con una I. Nos quedan nueve espacios por llenar. Podemos llenar tres de ellos con una I en $\binom{9}{3}$ formas. Esto nos deja seis espacios para llenar con las cuatro S y las dos P. Como la primera S debe aparecer antes de la primera P, debemos llenar la posición abierta más a la izquierda con una S. Esto nos deja con cinco espacios para llenar. Podemos llenar tres de ellos con las restantes S en $\binom{5}{3}$ formas. Podemos colocar las dos P en las dos posiciones restantes de una manera. Por lo tanto, el número de permutaciones de MISSISSIPPI en las que la primera I aparece antes de la primera S y la primera S aparece antes de la primera P es $$11\binom{9}{3}\binom{5}{3}$$