|
I thought the problem was easy. I had a simple solution that turned out to be wrong. Charlie gives the exact answer of 39480. The following is an analytic solution:
There are a total of 10!/2^5=113400 of arranging 2 each of A, B, C, D, E. I will subtract the number ways of having one or more consecutive pairs.
Consider forcing there to be exactly one pair. This could look like
AA--------
-AA------- etc. The AA could go in 9 positions, there are 5 letters that could be here, and there are 8!/2^4 ways of placing the other letters.
9*5*8!/2^4=113400.
113400-113400=0
But this is an overcount by all the ways of having two or more pairs. So we need to count these
AA-------- and --------AA give 7 positions for the 3rd pair
--AA------ through -------AA- each give 6. For a total of 56. There are 5C2=10 pairs of letters that could be here and 6!/2^3=90 ways of placing the other letters.
56*10*90=50400
113400-113400+50400=50400
Again this is an overcount of the ways of having 3 or more pairs. This count is more complicated.
AABB------ gives 5 places for the 3rd pair and shifting the BB gives 5+4+4+4+4+4+5=30 total.
-AA------- gives 4+3+3+3+3+4=20
--AA------ gives 5+4+3+3+3+4=22
---AA----- gives 4+4+4+3+3+4=22
----AA---- gives 4+3+4+4+3+4=22
Using symmetry we can compute the grand total here as 30+20+22+22+22+22+22+20+30=210. There are 5C3=10 triples of letters that could be here and 4!/2^2=6 ways of placing the remaining 4 letters.
210*10*6=12600
113400-113400+50400-12600=37800
Again this is an overcount of the ways of having 4 or more pairs. Another complicated count but I will not go into too much detail.
AA-------- when considering all the places for BB and then CC gives a total of 60 places for the four pairs.
-AA------- etc. yield 24, 42, 36, 36, 36, 42, 24 and 60
The total here is 360, 5C4=4 possible quartets of letters and there is 1 way of placing the remaining letters.
360*5*1=1800
113400-113400+50400-12600+1800=39600
Finally this is an overcount of the ways of having all five pairs. There are 5!=120 ways of doing this. The final count is:
113400-113400+50400-12600+1800-120=39480. |
