# Permutation Problem

• Jan 1st 2010, 06:57 AM
mcroldan08
Permutation Problem
Problem: In how many ways can these letters EFGHIEFGHI be arranged if the same letter musn't appear next to each other?

since we have 2 E's, F's, G's, H's and I's... The formula should be

10!
------------- = 113400 ways
2!2!2!2!2!

Then I combine similar letters [EE]FGHIFGHI for 5 letters

9!x5
-------- = 113400 ways
2!2!2!2!

That's where i get stumped... need help... XD
• Jan 1st 2010, 07:28 AM
Plato
Quote:

Originally Posted by mcroldan08
Problem: In how many ways can these letters EFGHIEFGHI be arranged if the same letter musn't appear next to each other?

You have started it correctly. Now we apply the inclusion/exclusion rule.
$\sum\limits_{k = 0}^5 {\left( { - 1} \right)^k \binom{5}{k}\frac{{\left( {10 - k}\right)!}}{{2^{5 - k} }}}$
• Jan 1st 2010, 07:31 AM
mcroldan08
uhmm... could you walk me through that rule... I'm not familiar with it... XD
• Jan 1st 2010, 07:45 AM
Plato
Quote:

Originally Posted by mcroldan08
uhmm... could you walk me through that rule... I'm not familiar with it... XD

If that is true, then I must wonder why you are asked to do this problem?
Inclusion-Exclusion Principle -- from Wolfram MathWorld
• Jan 1st 2010, 07:58 AM
mcroldan08
=n(A) + n(B) + n(C) + n(D) + n(E) - n (A&B) - n(A&C) - n(A&D) - ... - n(A&B&C) - n(B&C&D) - ... - n(A&B&C&D) - n(A&B&C&E) - ... + n(A and B and C and D and E)

Is this right?? XD
• Jan 1st 2010, 08:00 AM
Plato
Quote:

Originally Posted by mcroldan08
=n(A) + n(B) + n(C) + n(D) + n(E) - n (A&B) - n(A&C) - n(A&D) - ... - n(A&B&C) - n(B&C&D) - ... - n(A&B&C&D) - n(A&B&C&E) - ... + n(A and B and C and D and E)

Is this right?? XD

That is the basic idea.
• Jan 1st 2010, 08:05 AM
mcroldan08
Got it...

Final Check...

= 5x9!/2!2!2!2! - 10x(8!/2!2!2!) - 10x(7!/2!2!) - 5x(6!/2!) + 5!
=48720

so 113400-48720 = 64680...

anything I messed up??

btw... A heap of thanks!! really really appreciated the help... (Nod)(Rock)
• Jan 1st 2010, 08:11 AM
Plato
Quote:

Originally Posted by mcroldan08
Got it...

Final Check...

= 5x9!/2!2!2!2! - 10x(8!/2!2!2!) - 10x(7!/2!2!) - 5x(6!/2!) + 5!

anything I messed up??

You missed a sign. It should be +.
• Jan 1st 2010, 08:18 AM
mcroldan08
Ok.. Got it!! Thanks a lot!! (Rock)