2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – tychicus Jul 10 '13 at 11:16
  • $\begingroup$ You're correct. Change made. $\endgroup$ – Rick Decker Jul 10 '13 at 12:54
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.