Las permutaciones de MISSISSIPPI que no contienen letras idénticas adyacentes

Question

¿En cuántos arreglos de las letras de la palabra $MISSISSIPPI$ ¿no hay dos letras idénticas paradas una al lado de la otra?

Podemos usar el principio de inclusión y exclusión, pero hay demasiados conjuntos para considerar. Por ejemplo, necesitamos contar aquellas permutaciones en las que $(SSSS)$ , $((SSS), (S))$ ocurren pero no juntos, $((SS), (SS))$ ocurren pero no juntos, etc., y de manera similar para $I$ s. El problema es de Conteo y Configuraciones de Jiri Herman, Radon Kucera y Jaromir Simsa. El libro deriva una expresión complicada similar a la fórmula de inversión de Mobius y la usa para obtener la respuesta. ¿Hay una forma más simple? La respuesta a la pregunta actual es 2016.

Answer 1

Para ello puede utilizar la inclusión-exclusión. Así es como se hace:

Las letras forman un conjunto múltiple:

$$\mathfrak{W}_m=\{M^1,I^4,S^4,P^2\}$$

En primer lugar, marque las letras con sufijos para poder distinguirlas (dividiremos las permutaciones duplicadas en el resultado). Así tenemos el conjunto:

$$\mathfrak{W}_s=\{M,I_1,I_2,I_3,I_4,S_1,S_2,S_3,S_4,P_1,P_2\}$$

Tenemos, por tanto, 4 cartas de diferente tipos .

Entonces el principio de inclusión-exclusión da (después de dividir las permutaciones de letras idénticas):

$$\#(\text{valid permutations of $\mathfrak {W}_m $})=\frac{1}{1!4!^22!}\sum_{k=0}^{7} (-1)^kS_k\tag{1}$$

donde $S_k$ es la suma de todas las cardinalidades de las intersecciones de subconjuntos de permutaciones de $\mathfrak{W}_s$ con al menos $k$ pares de letras adyacentes ordenadas del mismo amable .

Debe quedar claro que una carta amable con $n$ las cartas pueden tener $r$ pares de letras adyacentes ordenadas y seleccionadas en $\binom{n-1}{r}\frac{n!}{(n-r)!}$ formas: Fuera de $n!$ permutaciones que elegimos $r$ de la $n-1$ pares adyacentes en cada uno. A continuación, dividir por el $(n-r)!$ disposiciones de la $n-r$ bloques de letras que producen selecciones idénticas. Por lo tanto:

$$\begin{align}(-1)^kS_k=&(11-k)!\times\\[1ex] &\sum_{k=r_1+r_2+r_3} (-1)^{r_1}\binom{3}{r_1}\frac{4!}{(4-r_1)!}(-1)^{r_2}\binom{3}{r_2}\frac{4!}{(4-r_2)!}(-1)^{r_3}\binom{1}{r_3}\frac{2!}{(2-r_3)!}\, .\end{align}$$

Podemos ver que $(-1)^kS_k$ equivale a la $x^{11-k}$ coeficiente del producto

$$(11-k)!x\left(\binom{3}{0}\frac{4!}{4!}x^4-\binom{3}{1}\frac{4!}{3!}x^3+\binom{3}{2}\frac{4!}{2!}x^2-\binom{3}{3}\frac{4!}{1!}x\right)^2\left(\binom{1}{0}\frac{2!}{2!}x^2-\binom{1}{1}\frac{2!}{1!}x\right)\, .$$

Así, $(1)$ se convierte (utilizando la función "encontrar $x^m$ operador de coeficiente" $[x^m]$ ):

$$\begin{align}&\left(\sum_{k=0}^{7}(11-k)![x^{11-k}]\right)x\left(\frac{1}{24}x^4-\frac{1}{2}x^3+\frac{3}{2}x^2-x\right)^2\left(\frac{1}{2}x^2-x\right)\\[1ex] &=\frac{1}{1152} \, 11! - \frac{13}{576} \, 10! + \frac{11}{48} \, 9! - \frac{7}{6} \, 8! + \frac{77}{24} \, 7! - \frac{19}{4} \, 6! + \frac{7}{2} \, 5! - 4!\, ,\end{align}$$

que usted puede verificar es $2016$ .