# Probability of getting some kinds of balls

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!

-
why do the balls have the number infinity on all of them, this doesn't seem like important information.....or am I missing something? – Squirtle Sep 8 '12 at 15:06
@dustanalysis: Typically when a class of objects has a "number", what is meant is that there are that certain number of them (at least in common English usage). – Nicolás Kim Sep 8 '12 at 15:14
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. – Graphth Sep 8 '12 at 15:30

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}}$$
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.. – Benson Sep 8 '12 at 18:17