# 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). 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? 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. 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. Aug 12, 2016 at 12:46