Permutations with no two adjacent numbers being equal I have been struggeling for some time with the following exercise from a book in discrete mathematics. It is an inclusion-exclusion principle exercise.
How many permutations of 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 are there in which no two adjacent numbers are equal?
I have come thus far:
Let S be the set of all permutations of 1, 1, 2, 2, 3, 3, 4, 4, 5, 5. Let $P_{i}$ be the property: pattern $ii$ occurs, for $i ≤ 5$. Then $|S|=(2!)^{5}$. I divide by $(2!)^{5}$ to not overcount the cases where two equal numbers come one after the other. There are 4 such cases.
$|S|-\sum_{i<j}N(i,j)+\sum_{i<j<k}N(i,j,k)-\sum_{i<j<k<l}N(i,j,k,l)+\sum N(1,2,3,4,5)$
Let $N(i)$ be the number of members of $S$ having property $P_{i}$. Then $N(1)=N(2)=N(3)=N(4)=N(5)=\frac{9!}{(2!)^{4}}$. There are 9 choices for placing i.e. $11$ in a permutation. The remaining eigth numbers may be permuted in 8! ways. I divide by $(2!)^{4}$ not to overcount the cases where two equal numbers are adjacent. Which one comes first doesn't matter.
When it comes to each $N(i,j)$ etc. I get stuck. The solution says $N(i,j)=\frac{8!}{2^3}$ but I don't understand why.
 A: You're almost there, modulo one small error in your displayed expression. Let's fix that first.
Let $S_i$ be the set of all the permutations which contain an adjacent pair $ii$ and let $S$ be the set of all possible permutations on $1,1,2,2,3,3,4,4,5,5$. You correctly realize that you want to find
$$
|S| - |S_1\cup S_1\cup S_3\cup S_4\cup S_5|
$$
Let's get the expression on the left and later subtract it from $|S|$. The inclusion-exclusion principle tells us
$$
\begin{align}
|S_1\cup S_1\cup S_3\cup S_4\cup S_5| &= |S_1| + |S_2|+\cdots + |S_5|\\
 &- |S_1\cap S_2|-\dots - |S_4\cap S_5| \\
 &+ |S_1\cap S_2\cap S_3| +\cdots+|S_3\cap S_4\cap S_5|\\
 &- |S_1\cap S_2\cap S_3\cap S_4|-\cdots - |S_2\cap S_3\cap S_4\cap S_5|\\
 &+ |S_1\cap S_2\cap S_3\cap S_4\cap S_5|
\end{align}
$$
which is almost what you had, except you missed the singleton terms. In your notation, then, we'll have
$$
\begin{align}
|S_1\cup \cdots \cup S_5| &= \sum N(i)\\
&-\sum N(i, j)\\
&+\sum N(i,j,k)\\
&-\sum N(i, j, k, l)\\
&+\sum N(i,j,k,l,m)
\end{align}
$$
Now you correctly figured out that $N(i) = 9!/2^4$. One way to look at this is that, say, $N(1)$ is number of permutations of the 9-element set $(11),2,2,3,3,4,4,5,5$, where we treat the adjacent $1$s as a single element.
Then we can look at $N(i,j)$ as the permutations of the 8-element set consisting of the paired elements $(ii),(jj)$, along with the 6 omitted elements. By the same reasoning you used in the derivation above, we'll have $N(i, j)=8!/2^3$ and similarly, we'll have $N(i,j,k)=7!/2^2$, $N(i,j,k,l)=6!/2$ and $N(1, 2, 3, 4, 5)=5!$.
Now there will be $\binom{5}{1}$ of the $N(i)$, $\binom{5}{2}$ of the $N(i, j)$ and so on, so we have
$$
|S_1\cup\dots\cup S_5|=\sum_{k=1}^5(-1)^{k+1}\binom{5}{k}\frac{(10-k)!}{2^{5-k}}
$$
so, finally, we see that the number of permutations with no adjacent equal numbers will be
$$
\begin{align}
|S|-|S_1\cup\dots\cup S_5|&=\frac{10!}{2^5}-\sum_{k=1}^5(-1)^{k+1}\binom{5}{k}\frac{(10-k)!}{2^{5-k}}
\end{align}
$$
which, assuming I did the calculations correctly, is 39480, for what it's worth.
A: I have not used the inclusion exclusion method but on solving I got it to be like this
$$ \frac{10!}{(2!)^5}- \left\{\frac{ 5×9!}{(2!)^4} + \frac{10×8!}{(2!)^3} + \frac{10×7!}{(2!)^2} + \frac{5×6!}{(2!)}\right\}.$$
