¿Cómo puedo saber cuántos anagramas de mississippi no contienen la palabra psi?

Question

Estoy muy confundido sobre cómo calcular esto. Sé que es el número de permutaciones de mississippi menos el número de permutaciones que contienen psi, pero teniendo en cuenta que hay repeticiones de esas letras, no estoy seguro de cómo lo haría.

Answer 1

La propiedad de "contener una palabra como subcadena" me resulta bastante difícil de modelar matemáticamente sin contarla. Me pregunto si existe una solución más agradable.

De todos modos: estrategia básica: contar permutaciones de MISSISSIPPI - permutaciones de la forma PSIXXXXXX - permutaciones de la forma XPSIXXXXXXX - ... - permutaciones de la forma XXXXXXXXPSI + permutaciones con dos copias de la palabra PSI (nótese que no tenemos que preocuparnos por las permutaciones con tres copias de la palabra PSI, ya que sólo hay dos Ps en MISSISSIPPI).

Ejecución:

permutaciones de MISSISSIPPI = $\dfrac{11!}{4!4!2!}$

permutaciones de MISSISSIPPI empezando por la palabra PSI = permutaciones de las letras restantes, que son MPSSSIII = $\dfrac{8!}{3!3!}$

multiplicamos este número por $9$ para las posibles primeras posiciones de P.

Ahora tenemos que contar los PSI dobles.

Si hay un doble PSI, hay 21 posibilidades para la ubicación del doble P $(1, 4)$ a través de $(1, 9)$ , $(2, 5)$ a través de $(2, 9)$ , ..., $(6, 9)$ .

Para cada una de estas posibilidades, las letras restantes son sólo permutaciones de MSSII de las cuales hay $\dfrac{5!}{2!2!}$ .

Así que la respuesta "definitiva", entre comillas porque probablemente me he equivocado, es

$$ \frac{11!}{4!4!2!} - 9\frac{8!}{3!3!} + 21\frac{5!}{2!2!} $$

Answer 2

Se parte de las permutaciones del conjunto de letras, y se trabaja eliminando las repeticiones. Vamos a empezar, trabajando lentamente.

Su conjunto está compuesto por las letras de la palabra: $S={M,I,S,S,I,S,S,I,P,P,I}$ Este conjunto tiene cardinalidad (número de elementos): $|S|=11$

Este juego tiene $P_{11}=11!=39916800$ permutaciones.

Ahora, hay que eliminar las repeticiones causadas por las permutaciones de la misma letra. Imagina la permutación: MIIIISSSSPP. Tendrás permutaciones que se verán igual cuando:

• Cambias las dos Ps
• Se cambian las cuatro "S" entre ellas
• Cambias las cuatro Is entre ellas

¿Cuántos habrá de estos? Es un subproblema de combinatoria. Hay dos Ps, cuatro Ss y cuatro Is, así que tienes $P_2=2!=2$ permutaciones para las Ps y $P_4=4!=24$ para los Is y de nuevo para los Ss. Tiene $2\times24\times24=1152$ permutaciones de letras iguales, por patrón .

Tenga en cuenta que estas repeticiones se producen para cada patrón diferente. Usted tiene $1152$ repeticiones que resultan en MIIIISSSSPP, pero tiene otra $1152$ que resultan en MIIPPSSSS. Para eliminar las repeticiones, hay que dividir el $39916800$ obtenida anteriormente por $1152$ en lugar de restar $1152$ de la $39916800$ (que es un error común para los principiantes).

Así que, a estas alturas, ya sabemos cuántas permutaciones sin repetición hay de $S={M,I,S,S,I,S,S,I,P,P,I}$ . Hay $\frac{P_{11}}{P_2 \times P_4 \times P_4}=\frac{39916800}{1152}=34650$ .

La última parte consiste en resolver el subproblema de cuántas permutaciones de MISSISSIPPI contienen PSI. Esto es bastante sencillo. Es el mismo problema que el anterior, pero con este conjunto $S={PSI,M,I,I,I,S,S,S,P}$ . Este conjunto tiene cardinalidad 9, por lo que tiene $P_9=9!$ permutaciones, de las que hay que eliminar las repeticiones causadas por el intercambio de letras iguales (tres Is, tres S). Estas repeticiones son $P_3 \times P_3=3!\times3!=36$ por patrón, así que al igual que antes, dividimos $\frac{P_9}{P_3 \times P_3}=10080$

Ahora, hay un pequeño inconveniente. Las permutaciones anteriores producirán, por ejemplo, este patrón: PSIMIISSPSI. Notarás que PSI aparece dos veces. Para cada una de ellas, habrá una repetición, cuando el primer PSI se intercambie con el último PSI. Tenemos que eliminarlas. ¿Cuántas hay? De nuevo, el mismo método: $S={PSI,PSI,M,I,I,S,S}$ cardinalidad $|S|=7$ con repeticiones causadas por los dos PSI, los dos Is y los dos S. El número de permutaciones sin repetición es $\frac{P_7}{P_2 \times P_2 \times P_2}=\frac{7!}{8}=630$ .

El número de permutaciones de MISSISSIPPI que contienen El PSI es $10080-630=9450$ .

La respuesta final es el número de permutaciones sin repeticiones de MISSISSIPPI menos el número de permutaciones sin repeticiones de PSI y las letras MIIISSSP, después de eliminar los duplicados causados por dos PSI: $34650-(10080-630)=25200$ .

Salvo error de cálculo, ésta es la respuesta.

Answer 3

La solución más sencilla es muy similar a la del usuario29743. El truco para contar las permutaciones que contienen un número determinado de copias de "PSI" es tratar cada "PSI" como un solo símbolo. Queremos

(# de permutaciones de MISSISSIPPI) - (# de permutaciones de [PSI]SSSIIIMP) + (# de permutaciones de [PSI][PSI]SSIIM)

$$= {11\choose 4,4,2,1} - {9\choose 3,3,1,1,1} + {7\choose2,2,2,1} = 25200.$$

Answer 4

Esto se puede calcular directamente en GAP mediante el siguiente código:

L:=["m","i","s","s","i","s","s","i","p","p","i"];;
S:=PermutationsList(L);;
n:=Size(L);;
T:=Filtered(S,M->not ForAny([1..n-2],i->M[i]="p" and M[i+1]="s" and M[i+2]="i"));;
Print(Size(T),"\n");

Esto devuelve 25200 anagramas de "mississippi" que no contienen "psi", confirmando la respuesta de countinghaus.