3
$\begingroup$

Find the number of ways of arranging four blue, three green and two red balls such that no two blue balls are adjacent.

I have done this question and got the answer which is $$\binom{6}{4} \cdot \frac{5!}{2!\cdot3!}=150$$ using the concept of arranging $4$ blue balls in the six vacant spaces among the five other balls.

How can this problem be solved by excluding combinations which consist of $4$ blue balls together, $3$ blue balls together, or two blue balls together?

$\endgroup$
1
$\begingroup$

There are $4 + 3 + 2 = 9$ positions to fill. We fill four of them with blue balls, three of the remaining five positions with green balls, and the remaining two positions with red balls. Therefore, the number of possible arrangements of the balls is $$\binom{9}{4}\binom{5}{3}\binom{2}{2} = \frac{9!}{4!5!} \cdot \frac{5!}{3!2!} \cdot \frac{2!}{2!0!} = \frac{9!}{4!3!2!}$$ From these, we wish to exclude those arrangements with one or more pairs of adjacent blue balls. Since there are only four blue balls, at most three such pairs can be formed.

A pair of adjacent blue balls: We have eight objects to arrange: $bb$, $b$, $b$, $g$, $g$, $g$, $r$, $r$. We choose three of those eight positions for the green balls, two of the remaining five positions for the red balls, two of the remaining three positions for the blue balls, and place the block of two blue balls in the remaining position. Hence, there are $$\binom{8}{3}\binom{5}{2}\binom{3}{2}\binom{1}{1} = \frac{8!}{3!2!2!}$$ such arrangements.

If we subtract the number of arrangements with a pair of adjacent blue balls from the total, we will have subtracted too much since we will have subtracted those arrangements with two pairs of adjacent blue balls twice, once for each way of designating one of those pairs as the pair of adjacent blue balls. Since we only want to subtract such arrangements once, we must add them back.

Two pairs of adjacent blue balls: This can occur in two ways.

  1. There are two disjoint pairs of adjacent blue balls.
  2. There are two overlapping pairs of adjacent blue balls, meaning that there are three consecutive blue balls.

Two disjoint pairs of adjacent blue balls: We have seven objects to arrange: $bb$, $bb$, $g$, $g$, $g$, $r$, $r$. We choose two of the seven positions for the blocks of blue balls, three of the remaining five positions for the blocks of green balls, and then fill the remaining the two positions with the red balls. Hence, there are $$\binom{7}{2}\binom{5}{3}\binom{2}{2} = \frac{7!}{2!3!2!}$$ such arrangements.

Two overlapping pairs of adjacent blue balls: We again have seven objects to arrange: $bbb$, $b$, $g$, $g$, $g$, $r$, $r$. We choose three of the seven positions for the green balls, two of the remaining four positions for the red balls, and arrange the remaining two distinct objects in the remaining two positions. Hence, there are $$\binom{7}{3}\binom{4}{2}2! = \frac{7!}{3!4!} \cdot \frac{4!}{2!2!} \cdot 2! = \frac{7!}{3!2!}$$ such arrangements.

If we subtract the number of arrangements containing a pair of adjacent blue balls and add the number of arrangements containing two pairs of adjacent blue balls, we will have not subtracted arrangements containing three pairs of adjacent blue balls at all. This is because we subtract three times when we subtract arrangements containing a pair of adjacent blue balls, once for each way we could designate one of those pairs as the pair of adjacent blue balls, and add them three times when we add arrangements containing two pairs of adjacent blue balls, once for each of the $\binom{3}{2}$ ways we could designate two of the three pairs as the pairs of adjacent blue balls. Hence, we must subtract the number of arrangements with three pairs of adjacent blue balls from the total.

Three pairs of adjacent blue balls: This means all four blue balls are consecutive. Hence, we have six objects to arrange: $bbbb$, $g$, $g$, $g$, $r$, $r$. We choose three of the six positions for the green balls, two of the remaining three positions for the red balls, and fill the final position with the block of blue balls. Hence, there are $$\binom{6}{3}\binom{3}{2}\binom{1}{1} = \frac{6!}{3!2!}$$ such arrangements.

By the Inclusion-Exclusion Principle, the number of arrangements of four blue, three green, and two red balls in which no two blue balls are consecutive is $$\frac{9!}{4!3!2!} - \frac{8!}{3!2!2!} + \frac{7!}{2!3!2!} + \frac{7!}{3!2!} - \frac{6!}{3!2!} = 150$$ which agrees with your result.

$\endgroup$
  • $\begingroup$ @SamarImamZaidi There was an error in my original answer to this problem. I was missing a factor of $2!$ in the denominator of one of the terms. I corrected the error yesterday. $\endgroup$ – N. F. Taussig Mar 16 '18 at 15:04

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.