Permutations of MISSISSIPPI not containing adjacent identical letters In how many arrangements of the letters of the word $MISSISSIPPI$ are no two identical letters stand next to each other?
We can use Inclusion Exclusion principle but there are too many  number of sets to consider. For example, we need to count those permutations in which $(SSSS)$, $((SSS), (S))$ occur but not together, $((SS), (SS))$, occur but not together etc. and similarly for $I$s. The problem is from Counting and Configurations by Jiri Herman, Radan Kucera and Jaromir Simsa. The book derives a complicated expression similar to Mobius Inversion formula and uses it to obtain the answer. Is there a simpler way? The answer to the current question is 2016.
 A: You can use Inclusion-Exclusion for this. Here's how:
The letters comprise a multiset:
$$\mathfrak{W}_m=\{M^1,I^4,S^4,P^2\}$$
Firstly mark the letters with suffixes thus making them distinguishable (we will divide out duplicate permutations in the result). Thus we have the set:
$$\mathfrak{W}_s=\{M,I_1,I_2,I_3,I_4,S_1,S_2,S_3,S_4,P_1,P_2\}$$
We have, therefore, 4 letters of different kinds.
Then the inclusion-exclusion principle gives (after dividing out permutations of identical letters):
$$\#(\text{valid permutations of $\mathfrak{W}_m$})=\frac{1}{1!4!^22!}\sum_{k=0}^{7} (-1)^kS_k\tag{1}$$
where $S_k$ is the sum of all cardinalities of subset intersections of permutations of $\mathfrak{W}_s$ with at least $k$ ordered adjacent letter pairs of the same kind.
It should be clear that a letter kind with $n$ letters may have $r$ pairs of ordered adjacent letters selected in $\binom{n-1}{r}\frac{n!}{(n-r)!}$ ways: Out of $n!$ permutations we choose $r$ of the $n-1$ adjacent pairs in each. Then divide by the $(n-r)!$ arrangements of the $n-r$ blocks of letters which produce identical selections. Hence:
$$\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}$$
We can see that $(-1)^kS_k$ is equivalent to the $x^{11-k}$ coefficient of the product
$$(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)\, .$$
Thus $(1)$ becomes (using the "find $x^m$ coefficient operator" $[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}$$
which you may verify is $2016$.
