Permutation with Duplicates

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.

-

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.

-
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