2
$\begingroup$

Suppose we have $N$ kinds of colored balls, and there are an infinite number of each kind. Now we'd like to draw $m(m>N)$ balls from them. How to calculate the probability P(m,n), which is the probability of drawing $n$ kinds of ball$(n\le N )$?

Below is my solution, which is only a recursive expression, I'm not sure whether it is true, and I hope someone can give me a closed form expression.

=my solution=

For $m, $P(m,n)=0$

For $n=1$, $P(m,n)=(\frac{1}{N})^{m-1}$

For $n>1$, $P(m,n)=P(m-1,n)*\frac{n}{N}+P(m-1,n-1)*\frac{N-n+1}{N}$

The first and second expression are quite obvious. for $P(m,n),m\ge n,n>1$, consider the first $m-1$ balls we drawn, if we've drawn $n$ kinds of balls, then the last ball we draw must belongs to the $n$ kinds of balls. Otherwise, the last ball must be chosen from the left $N-n+1$ kinds.

Thank you!

  • 1
    I agree with dustanalysis that it sounded like the number of each separate ball was infinity, which sounds like each is labeled infinity. Whereas, with the new edit, it is now clear that the meaning is an infinite number of each kind.2012-09-08

1 Answers 1

5

The number of ways to chose $m$ balls out of $N$ distinct types is equal to the number of ways to put $m$ coins into $N$ cells (the number of coins in each cell tells us how many balls of this type were chosen). So it is $\binom{m+N-1}{m}=\binom{m+N-1}{N-1}$.
The number of ways to get exactly $n$ distinct types is to choose the $n$-types, i.e. $\binom{N}{n}$, and then to distribute those $m$ coins between $n$ cells, such that no cell is empty. That is, put $1$ coin into each of the $n$ cells. You have still $m-n$ coins to put into $n$ cells. So you have $\binom{N}{n}\binom{m-n+n-1}{n-1}=\binom{N}{n}\binom{m-1}{n-1}$. So your probability will be: $P(m,n)=\frac{\binom{N}{n}\binom{m-1}{n-1}}{\binom{m+N-1}{m}}$

  • 0
    Thank you, Dennis. Seems my recursive answer is wrong(by replacing $m,n,N$ with certain numbers). but I still not quite sure why it's wrong..2012-09-08