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<n$, $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!
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}}$$