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

Question

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.

Answer 1

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)
    return total

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