1. ## Inclusion/Exclusion Question

Hi. I'm struggling with this question from the section on the inclusion/exclusion principle:

"How many arrangements of the numbers 1, 1, 2, 2, 3, 3, 4, 4 are there in which no adjacent numbers are equal?"

My thought was to try and find the total arrangements possible, then subtract off the number of arrangements with at least 2 numbers equal, the latter being calculated with the help of inclusion/exclusion.

Calculating the total arrangements seems easy: C(8,2)*C(6,2)*C(4,2)*C(2,2)

But the other part seems complicated. My first attempt was to divide the eight slots into 7 pairs of adjacent slots. Then A_x is the number of arrangments that make pair x equal. But then, I have to go seven levels deep in applying inclusion/exclusion, and I'm doing about half a page of careful case calculation before even finishing n_2. When a counting problem gets highly complicated and calculation intensive, that usually means I'm taking the wrong approach.

2. ## Re: Inclusion/Exclusion Question

Originally Posted by infraRed
"How many arrangements of the numbers 1, 1, 2, 2, 3, 3, 4, 4 are there in which no adjacent numbers are equal?"
The total possible number of arrangements is $\dfrac{8!}{2^4}$.

The number in the one's are together is equal to $\dfrac{7!}{2^3}$

Inclusion/exclusion $\displaystyle\sum\limits_{k = 0}^4 {{{\left( { - 1} \right)}^k}\dbinom{4}{k}\dfrac{{\left( {8 - k} \right)!}}{{{2^{4 - k}}}}}$

3. ## Re: Inclusion/Exclusion Question

Originally Posted by Plato
The total possible number of arrangements is $\dfrac{8!}{2^4}$.

The number in the one's are together is equal to $\dfrac{7!}{2^3}$

Inclusion/exclusion $\displaystyle\sum\limits_{k = 0}^4 {{{\left( { - 1} \right)}^k}\dbinom{4}{k}\dfrac{{\left( {8 - k} \right)!}}{{{2^{4 - k}}}}}$
Thank you much for the help. However, is it possible you could explain some more about how you came up with those numbers? I imagine you are correct, but I have little understanding at this point.

4. ## Re: Inclusion/Exclusion Question

Originally Posted by infraRed
Thank you much for the help. However, is it possible you could explain some more about how you came up with those numbers? I imagine you are correct, but I have little understanding at this point.
Lets change to $AABBCCDD$, no two identical letters together.

Think of $AA$ as one 'packet'. So instead of eight we have seven letters to rearrange.
So, there are $\dfrac{7!}{2^3}$ ways to arrange the string in which the $AA$ appears.

There are $\dfrac{6!}{2^2}$ ways to arrange the string in which the $AA~\&~BB$ appear.

Using inclusion/exclusion we calculate the number of ways for at least one of $AA,~BB,~CC,~DD$ appears.