2
$\begingroup$

I have $5$ white balls and $3$ red balls. Putting these $8$ balls in a row with no adjacent red balls, what is the number of arrangements?

My approach:

I tried the inclusive-exclusive method, by getting all the possible arrangements and then subtracting from the number of times the red ones would be together:

Total: $$\frac{8!}{5! 3!} = 56$$

Then, I ''glued'' together all the red ones, making it $1$ red ball and $5$ white balls:

$$\frac{6!}{5! 1!} = 6$$

And finally, I glued one pair of red balls and left one alone, making it:

$$\frac{7!}{5!1!1!} = 42$$

Subtracting the above from the total would give $8$ arrangements, but actually the answer is $20$. I would appreciate knowing if my approach is correct, or else, what I'm doing wrong to solve this question.

$\endgroup$
  • 4
    $\begingroup$ As for a correct approach... Begin by placing the five white balls in a row. Then, leave a little bit of extra space between each white ball: e.g. $\underline{~}W\underline{~}W\underline{~}W\underline{~}W\underline{~}W\underline{~}$. Now... pick three of those spaces simultaneously to be used by the red balls, noting that the order in which you pick those spaces does not matter and that you cannot repeat your selections... i.e. binomial coefficients will be the correct tool to use here. This gives $\binom{6}{3}=20$ arrangements, agreeing with the given answer. $\endgroup$ – JMoravitz Apr 21 '18 at 16:17
  • 2
    $\begingroup$ As for what you did wrong, let $\textbf{R}$ represent the three reds glued together, $R$ two reds, and $r$ one red. You counted the outcome $\textbf{R}wwwww$, $Rrwwwww$ and $rRwwwww$ all as separate outcomes despite all corresponding to the same outcome of the three reds appearing all at the beginning. Similarly other outcomes were overcounted as well. You could notice that those outcomes overcounted are exactly those outcomes where all three reds were together and they were counted exactly three times each. Correcting the count by adding back what was overcounted gives $8+6+6=20$ $\endgroup$ – JMoravitz Apr 21 '18 at 16:19
  • $\begingroup$ The first one comment for me could be classified as a answer, so thanks. But another question came to my mind. Would I be right if I said that the total number of arrangements are 8 choses 3, as stated above in my approach, or is it wrong as well? $\endgroup$ – Lucas Lemos Apr 21 '18 at 17:48
  • 2
    $\begingroup$ The total number of arrangements of 8 balls into a row, five of which are identical white balls and the remaining three of which are identical red balls, with no other restrictions is indeed 8 choose 3. $\endgroup$ – JMoravitz Apr 21 '18 at 17:50
2
$\begingroup$

Method 1: The approach @JMoravitz wrote in the comments is the easiest way to handle this problem. Place the white balls in a row. This creates six spaces, four between successive white balls and two at the ends of the row. $$\square w \square w \square w \square w \square w \square$$ To ensure that the red balls are separated, we must choose three of these six spaces in which to place a red ball, which can be done in $$\binom{6}{3} = 20$$ ways.

Method 2: We subtract those arrangements with two or more consecutive red balls from the total number of arrangements.

As you realized, the total number of arrangements is the number of ways we can select three of the eight positions for the red balls, which is $\binom{8}{3}$.

Arrangements with exactly two red balls together: Line up the five white balls in a row, creating six spaces, as shown above. Choose one of these spaces in which to place two adjacent red balls and one of the remaining five spaces in which to place the other red ball. Thus, there are $6 \cdot 5 = 30$ such arrangements.

Arrangements with all three red balls together: Line up the five white balls in a row, creating six spaces. Choose one of these six spaces in which to place the three red balls. There are $6$ such arrangements.

Hence, there are $$\binom{8}{3} - 6 \cdot 5 - 6 = 56 - 30 - 6 = 20$$ arrangements in which no two of the red balls are together.

Method 3: We use the Inclusion-Exclusion Principle.

As noted above, there are $\binom{8}{3}$ arrangements of five white and three red balls. From these, we must subtract those arrangements in which at least one pair of red balls is adjacent.

A pair of red balls is adjacent: We have seven objects to arrange, a block of two red balls, a single red ball, and five white balls. We choose five of the seven positions for the white balls, one of the remaining two for the single red ball, and place the block of two red balls in the final open position, which can be done in $$\binom{7}{5}\binom{2}{1}\binom{1}{1} = \frac{7!}{5!2!} \cdot \frac{2!}{1!1} \cdot \frac{1!}{1!0!} = \frac{7!}{5!} = 7 \cdot 6 = 42$$ such arrangements, as you found.

However, we have subtracted those arrangements in which there are two pairs of consecutive red balls (those arrangements with three consecutive red balls) twice, once when we designated the first two red balls as the pair of consecutive red balls and once when we designated the last two red balls as the pair of consecutive red balls. Therefore, we need to add arrangements with two pairs of consecutive red balls to the total. This is where you made your mistake.

Two pairs of consecutive red balls: Since there are only three red balls, this can only occur if all three red balls are consecutive. We showed above that there are $\binom{6}{1}$ such arrangements.

By the Inclusion-Exclusion Principle, the number of arrangements of five white and three red balls in which no two red balls are consecutive is $$\binom{8}{3} - \binom{7}{5}\binom{2}{1}\binom{1}{1} + \binom{6}{1} = 56 - 42 + 6 = 20$$

Method 4: @Lifeforbetter asked how to do this problem by first placing the red balls, then inserting the white balls.

Let $x_1$ be the number of white balls to the left of the first red ball; let $x_2$ be the number of white balls between the first and second red balls; let $x_3$ be the number of white balls between the second and third red balls; let $x_4$ be the number of white balls to the right of the third red ball. Since there are five white balls, $$x_1 + x_2 + x_3 + x_4 = 5 \tag{1}$$
Since no two of the red balls are adjacent, $x_2, x_3 \geq 1$, while $x_1, x_4 \geq 0$. Let $x_2' = x_2 - 1$; let $x_3' = x_3 - 1$. Then $x_2'$ and $x_3'$ are nonnegative integers. Substituting $x_2' + 1$ for $x_2$ and $x_3' + 1$ for $x_3$ in equation 1 yields \begin{align*} x_1 + x_2' + 1 + x_3' + 1 + x_4 & = 5\\ x_1 + x_2' + x_3' + x_4 & = 3 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers. A particular solution corresponds to the placement of $4 - 1 = 3$ addition signs in a row of $3$ ones. For instance, $$1 + + 1 1 +$$ corresponds to the solution $x_1 = 1$, $x_2' = 0$, $x_3' = 2$, $x_4 = 0$ ($x_1 = 1$, $x_2 = 1$, $x_3 = 3$, $x_4 = 0$). The number of such solutions is $$\binom{3 + 4 - 1}{4 - 1} = \binom{6}{3}$$ since we must choose which three of the six positions required for three ones and three addition signs will be filled with addition signs.

$\endgroup$
  • $\begingroup$ I tend to think R_R_R then find combinations of white balls. How to do it this way? $\endgroup$ – Lifeforbetter Sep 19 '19 at 15:32
  • 1
    $\begingroup$ @Lifeforbetter I have added a solution using your approach. $\endgroup$ – N. F. Taussig Sep 19 '19 at 16:17

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.