1
$\begingroup$

I want to arrange $3$ red balls, $2$ blue balls, and $2$ green balls in a line so that no two balls of the same color are adjacent. If there are no such restrictions, then the number of such unique arrangements is

$$\frac{7!}{3!\times 2!\times 2!}=210.$$

I found a related problem here but it does not have an answer. Instead, I wrote a code in R that will completely list all such possible arrangements. I found 38. I also tried to list them manually below.

  • _ B _ G _ B _ G _: $C^5_3=10$ arrangements
  • _ G _ B _ G _ B _: $C^5_3=10$ arrangements
  • _ G R G _ B R B _: 3 arrangements
  • _ B R B _ G R G _: 3 arrangements
  • _ G _ B R B _ G _: $C^4_2=6$ arrangements
  • _ B _ G R G _ B _: $C^4_2=6$ arrangements

Is this correct? Is there a more elegant way of doing this?

$\endgroup$
4
$\begingroup$

There are $10$ ways to arrange the red balls. Of these:

  1. two arrangements leave three adjacent free spots and one solo free spot: $$ R\,\_\,\_\,\_R\,\_R\\ R\,\_R\,\_\,\_\,\_R $$For each of these: Whichever colour is in the middle of the three free spots must also be in the solo spot, so 2 possibilities for each of these arrangements

  2. six arrangements leave two adjacent spots and two solo spots: $$ \,\_\,\_R\,\_R\,\_R\\ \,\_R\,\_\,\_R\,\_R\\ \,\_R\,\_R\,\_\,\_R\\ R\,\_\,\_R\,\_R\,\_\\ R\,\_R\,\_\,\_R\,\_\\ R\,\_R\,\_R\,\_\,\_ $$ and one leaves two pairs of adjacent spots: $$ R\,\_\,\_R\,\_\,\_R $$For each of these: the colours must differ in a pair of adjacent spots, but they can be swapped around, so 4 possibilities for each of these arrangements

  3. one arrangement leaves no adjacent spots: $$ \,\_R\,\_R\,\_R\,\_ $$ Here there are six possible arrangements of the remaining $4$ balls

In total: $$ 2\cdot 2 + 7\cdot 4 + 1\cdot 6 = 38 $$ I don't think there is a more "elegant" way to do this than simply splitting into cases and count. The interactions are too complicated to make inclusion-exclusion viable, and there isn't a simple formula for "non-adjacent" that we can apply. Of course, how you decide to split into cases changes how easy the calculations are and how easily you miss a case or double count.

$\endgroup$
  • 1
    $\begingroup$ Case 3 has only six arrangements of the remaining 4 balls, so your solution agrees with the original poster's. $\endgroup$ – Michael Nov 3 '17 at 12:30
  • $\begingroup$ @Michael You're right. $\endgroup$ – Arthur Nov 3 '17 at 12:36
  • $\begingroup$ This is a more systematic approach. Indeed, I think it is easier to miss or duplicate cases in my "manual" solution. $\endgroup$ – hpesoj626 Nov 3 '17 at 12:37
1
$\begingroup$

You might find applying inclusion-exclusion more "elegant"

Keeping the A's apart throughout, count the # of arrangements with

(A's apart) - (A's apart, B's or C's bunched) + (A's apart, both B's and C's bunched)

$ = \left[\frac{4!}{2!2!}\times \binom53 \right] - \left[2\times \frac{3!}{2!}\binom43\right] + \left[2!\times\binom33\right] = 60 - 2\cdot12 + 2 =38$

$\endgroup$
  • $\begingroup$ Definitely is! Thanks for taking your time to answer this. So insightful. $\endgroup$ – hpesoj626 Nov 4 '17 at 12:08
  • $\begingroup$ You are welcome ! $\endgroup$ – true blue anil Nov 4 '17 at 17:28

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.