6
$\begingroup$

In how many ways can the word "INDIVISIBILITY" be rearranged, such that no two Is come close to each other?

My attempt

Total number of ways of rearranging the word = $\dfrac{14!}{6!}$

Number of ways of rearranging the word such that at the least, a pair of Is come close to each other (the motivation for this comes from the negation of "no two Is come close to each other") = $\binom{6}{2} \times \dfrac{13!}{4!}$

Then, required number of arrangements = $\dfrac{14!}{6!} - \binom{6}{2} \times \dfrac{13!}{4!}$.

But this gives me a negative number. Where am I going wrong? Could anyone tell me how to go about this problem?

$\endgroup$
7
$\begingroup$

There are $8$ distinct letters, together with $6$ I's.

The $8$ non-I's can be arranged in $8!$ ways. Every such arrangement produces $9$ 'gaps" (the $7$ gaps between letters, and the $2$ 'endgaps") for us to slip a single I into. The $6$ gaps needed can be chosen in $\binom{9}{6}$ ways, for a total of $8!\binom{9}{6}$.

Remark: The $\binom{6}{2}\frac{13!}{4!}$ overcounts the cases where two or more I's are next to each other.

$\endgroup$
  • $\begingroup$ Oh, I see it now! Thank you for this remarkably simple solution. :) $\endgroup$ – Train Heartnet May 5 '15 at 7:06
  • 1
    $\begingroup$ You are welcome. The "gap" idea can be useful for problems in which we want no two consecutive objects of a certain type. $\endgroup$ – André Nicolas May 5 '15 at 7:09
1
$\begingroup$

You're counting some cases several times. For example, you're counting IIIINDVSBILITY both by putting the first II together and arranging the others, and putting the second II together and arranging the others.

What you need is to separate all the cases which is:

  • All the Is are next to each other.
  • Only 5 Is are next to each other.
  • Only 4 Is are next to each other.
  • 4 Is are next to each other and the two others are next to each other but apart from the first 4 Is
  • etc
$\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.