Is there an exact or recursive representation for the number of ways one can draw colored balls without putting them back?

Example

There are ten balls in an urn, six are red, three black and one white. $$n$$ balls are drawn from the urn without putting them back (of course, $$n \le 10$$). How many different permutations of the three colors (all balls of one color are indistinguishable) exist when not putting the balls back into the urn?

For $$n = 1$$, the result set $$\Omega$$ stays simple: $$\Omega_1 = \{r;b;w\}$$. The answer is $$|\Omega_1| = 3$$.

For $$n = 2$$, the result set looks like this: $$\Omega_2 = \{rr;rb;rw;br;bb;bw;wr;wb\}$$. The answer is $$|\Omega_2| = 8$$ and not $$3^n = 3^2 = 9$$ as expected when the balls would have been put back, because the white ball can not be drawn a second time.

For $$n = 3$$, we easily recognize how this problem can be calculated recursively. If a red or black ball is drawn as the first one, the remaining two have all the possibilities as in $$\Omega_2$$. If a white ball is drawn, the remaining two balls can not be white: $$\{wrr;wrb;wbr;wbb\}$$. This set is a subset of $$\Omega_3$$. The answer is $$|\Omega_3| = 2*|\Omega_2| + 4$$.

However, at $$n = 4$$ or $$n = 5$$, the black balls are also exceeded in some results which has to be taken into consideration when trying to calculate the number of results.

Generalizing

We are drawing $$n$$ balls out of an urn containing $$b$$ balls, without putting them back. There are $$k$$ different kinds of balls ($$k$$ different colors). For each color, there are $$b_i$$ balls in the urn: $$b_1 + b_2 + \dots + b_k = b$$.

This problem is very similar to this question, but "red-black" is a different result than "black-red", so one can not use the stars and bars method; knowing that we’ve drawn 3 red balls just isn’t enough.

Is there an exact or recursive representation of $$|\Omega_n|$$, either for the example above or general $$k$$, $$b$$ and $$b_1, b_2, \dots, b_k$$ ? If needed, a few conditions, or piecewise terms would be fine, but the formula would be prettier without them, of course.

Edit: The term "distinguishable permutation" (thanks to Cameron Buie) or "multiset permutation" is a great way to determine the answer for $$n = 10$$: $$\textit{840}$$. But wikipedia, besides mentioning the "k-permutation of a multiset" meaning a limited multiset permutation with only k draws, does not show a mathematical formula.

• Look up "distinguishable permutations" on wikipedia (or on this site). Commented Aug 12, 2016 at 11:46

The coefficient of $x^n$ in

$$n!\prod_{i=1}^{k}\left(\sum_{j=0}^{b_i}\frac{x^j}{j!}\right)$$

To use your example of $6,3,1$ balls:

$$n!\left(\frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \frac{x^5}{5!} + \frac{x^6}{6!}\right)\left(\frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}\right)\left(\frac{x^0}{0!} + \frac{x^1}{1!}\right)$$

Expanded:

$$n!\left(1 + 3x+ 4 x^2+\frac{10 x^3}{3}+\frac{47 x^4}{24}+\frac{101 x^5}{120}+\frac{11 x^6}{40}+\frac{17 x^7}{240}+\frac{7 x^8}{480}+\frac{x^9}{432} + \frac{x^{10}}{4320}\right)$$

There are $n!$ ways to arrange the $n$ balls that are drawn, but if we draw $j$ balls of any particular color, we must divide by $j!$ to render them indistinguishable amongst themselves.

Another way to solve this is with dynamic programming/memoization (Python script below):

@memoize
def draw(n, balls):
if n==0:
return 1
total = 0
for i in xrange(len(balls)):
if balls[i] > 0:
newBalls = balls[:]
newBalls[i]-=1
total += draw(n-1, newBalls)

balls = [6, 3, 1]
b = sum(balls)
for n in xrange(0, b+1):
print "n =", n, "ways =", draw(n, balls)


A quick table of results:

n = 0 ways = 1
n = 1 ways = 3
n = 2 ways = 8
n = 3 ways = 20
n = 4 ways = 47
n = 5 ways = 101
n = 6 ways = 198
n = 7 ways = 357
n = 8 ways = 588
n = 9 ways = 840
n = 10 ways = 840

• Thank you for the script; it's quite similar (in the way it operates) to what I would have thought of. Can you clarify what the x in your equations means, possibly by a full calculation for any specific n to show it matches the output of the script? Commented Aug 12, 2016 at 12:31
• Edited in an expanded version. For any particular $n$, just take the coefficient of $x^n$ and multiply it by $n!$. The $x$ itself doesn't matter (this is a generating function) -- the idea is that the coefficients of the polynomial accumulate / collect the terms corresponding to all choices that could possibly lead to it. Commented Aug 12, 2016 at 12:37
• I see! That's why the coefficient of $x^{10}$ is exactly one tenth of $x^9$. Because the result of $10!$ is exactly ten times $9!$. Thank you, this is such a clever solution. Commented Aug 12, 2016 at 12:46