Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I could swear I had a formula for this years ago in school, but I'm having trouble tracking it down. The problem:

I have 3 red balls and 3 black balls in a basket. I draw them out one at a time. How many different sequences of six balls can I get, i.e.

rbrbrb
rrrbbb
bbbrrr
etc...

I'm looking for a general formula for n red and m black. This is not a homework, just my aging brain trying to recover an abstract formula.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

Place the $n+m$ balls in a row; the pick which $m$ you want to be red. You have $\binom{n+m}{m}=\frac{(n+m)!}{n!m!}$ possible ways of doing it, so that is the formula in this case.

Here's an alternative way of thinking about it: place the $n$ red in a row; now you need to decide where to insert the $m$ black. What you want to do is choose the locations of the $m$ black balls; there are $n+1$ possible locations (before all the red balls, in the $n-1$ spaces between red balls, and after all the red balls). You want to pick those allowing repetitions, and without regard to the order in which you pick them (what matters is how many times you pick each gap).

The number of ways in which you can select $r$ items from $k$ possibilities, allowing repetitions and without regard to order (combinations with repetitions) is $\binom{k+r-1}{r}$.

So here you want to select $m$ out of $n+1$ possibilities, it gives $\binom{n+m}{m} = \frac{(n+m)!}{m!n!}$, same as before.

To see a derivation of the formula, see for example Wikipedia's article on combinations. This is sometimes also called the "stars and bars problem", so you can find a proof in the corresponding page.

share|improve this answer
    
Thanks. I was trying to model another problem in the abstract and this seemed like the right model. With your help, I was able to determine that it was the correct approach! –  Don Wakefield Dec 30 '10 at 4:18
    
@Don: Glad I could help. –  Arturo Magidin Dec 30 '10 at 4:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.