1
$\begingroup$

I'm trying to brush up a bit on basic combinatiorics and I'm finding that unfortunately I'm quite bad at it. I tried solving the following exercises without real success:

How many ways are there to arrange in a row 6 red balls, 6 yellow balls and 2 blue balls such that:

  1. The rightmost ball is red and there are no adjacent red balls.
  2. The rightmost ball is yellow and there are no adjacent red balls.
  3. There are no adjacent red balls and no adjacent blue balls

All my attempts were overly complicated and relied too much on brute force. I would really appreciate it if someone could show me how to elegantly approach such a question.

Note: I added the homework tag in hope it would get the question further exposure but this is not actually a homework task so if possible I'd prefer to see a complete solution rather than hints.

Thanks in advance!!

$\endgroup$
  • $\begingroup$ Are these three different questions, or one question with three different restrictions? $\endgroup$ – Eric Stucky Dec 23 '13 at 21:00
  • $\begingroup$ The 3 restrictions are mutually exclusive, so I think we can assume that it is 3 different problems, otherwise the answer would be trivial. $\endgroup$ – DanielV Dec 23 '13 at 21:18
1
$\begingroup$

Problems 1 and 2 are relatively easy to answer if you take the right approach. For problem 1, start by laying out the 6 yellow and 2 blue balls, with a space between consecutive balls. This can be done in $8\choose2$ ways. Now place one of the 6 red balls to the right of the yellow and blue balls and the other 5 in spaces to the left of them. This can be done in $8\choose5$ ways. Thus the answer is ${8\choose2}{8\choose5}=28\cdot56=1568$.

For problem 2, do basically the same thing, except this time when you lay out the yellow and blue balls, the rightmost ball must be yellow, so the number of choices for that step is $7\choose2$, and this time all 6 red balls must be placed to the left of a yellow or blue ball, giving $8\choose6$ choices for that step, for an answer of ${7\choose2}{8\choose6}=21\cdot28=588$.

I don't see a correspondingly slick way to handle problem 3, but you can break it down into two cases: When you lay down the yellow and blue balls, either the 2 blue balls are (temporarily) adjacent, in which case you need to insert a red ball between them, or they're not. Of the ${8\choose2}=28$ ways to lay down the yellow and blue balls, $7$ of them have the blue balls adjacent and $21$ do not. In the former case, after placing one red ball between the two blue balls, the other $5$ can go in any of $8$ places, while in the latter case, the $6$ red balls can go in any of $9$ places. Thus the answer to problem 3 is

$$7{8\choose5}+21{9\choose6}=7\cdot56+21\cdot84=2156$$

$\endgroup$
1
$\begingroup$

For the first, initially pretend the yellow and blue balls are the same color and put them all to the left of a red ball. There are now eight slots that you can put a red ball into, but only one or none in each slot. This is a classic stars and bars problem. Now pick two of the yellow/blue balls to be blue.

The second works about the same way.

For the last, calculate the total arrangements with no adjacent red balls (as above) and subtract the arrangements with no adjacent red balls and the blue balls adjacent. For the blue adjacent, it is the same as six red, six yellow, and one blue/blue arranged so no red balls are adjacent.

$\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.