2
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Marco
    Commented Aug 12, 2016 at 12:31
  • $\begingroup$ 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. $\endgroup$ Commented Aug 12, 2016 at 12:37
  • $\begingroup$ 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. $\endgroup$
    – Marco
    Commented Aug 12, 2016 at 12:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .