# 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.

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$. 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^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^k} \end{align} which, assuming I did the calculations correctly, is 39480, for what it's worth.

• Thanks a lot for a great explanation. However, I got the answer 39 480. $\frac{10!}{2^5}$ - $\binom{5}{1}\frac{9!}{(2!)^4}$ + $\binom{5}{2}\frac{8!}{(2!)^3}$ - $\binom{5}{3}\frac{7!}{(2!)^2}$ + $\binom{5}{4}\frac{6!}{(2!)^1}$ - $\binom{5}{5}\frac{5!}{(2!)^0}$ = 39 480. – tychicus Jul 10 '13 at 11:16
• You're correct. Change made. – Rick Decker Jul 10 '13 at 12:54

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\}.$$