1. ## permutation problem

I have seen the problem in this forum about 6 number 1,1,2,2,3,3 to be arranged in a line with no same adjacent numbers. The solution is 30. But what happens if there are 8 number 1,1,2,2,3,3,4,4? Are there any general rules and quick ways to solve? I have tried to 8!/(2!2!2!2!)- 4 pairs -3 pairs-2pairs - 1pair, but the computations are too cumbersome....any good ways to solve? please help

2. Originally Posted by taimanby
I have seen the problem in this forum about 6 number 1,1,2,2,3,3 to be arranged in a line with no same adjacent numbers. The solution is 30.
By use of inclusion/exclusion rule we count these by first counting the ones we don't want and substracting from the total.
For N pairs we have: $\sum\limits_{k = 0}^N {\left( { - 1} \right)^k {N \choose k} \frac{{\left( {2N - k}\right)!}}{{2^{N - k} }}}$

3. I've been racking my brain over this one, would you please flesh out your result/solution a bit more?

edit:
Nevermind, I see it now. Thanks.

4. thx for the enlightenment...many thanks...never think that problem can be categorised and solved so methodically..cheers

5. on second thoughts the solution is not right:
the formula can eb expanded when N =4 to:
8!/2^4-4C1.6!/2^3+...
the first term describes all possible combinations
but the 4C1.6!/2^3 only takes in the first 2 positions being a pair, and all possible combinations of the remaining 6 places.
similarly 3rd term only describes the first 4 places being 2 pairs, and all possible combinations of the remaining 4 places...
this does not account for x pair pair xx..
I think we have to work again.

rgds

6. Originally Posted by taimanby
on second thoughts the solution is not right:
the formula can eb expanded when N =4 to:
8!/2^4-4C1.6!/2^3+...
the first term describes all possible combinations
but the 4C1.6!/2^3 only takes in the first 2 positions being a pair, and all possible combinations of the remaining 6 places.
similarly 3rd term only describes the first 4 places being 2 pairs, and all possible combinations of the remaining 4 places...
this does not account for x pair pair xx..
I don't think that you understand this problem. It is a well known problem.
Here is a chart of the first 10 values.

7. thx Plato,,,the numeric answer are correct..i will look into the expression carefully again...It must be my misunderstanding....thx for yuoe help again...

ben