Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 5 down vote accepted

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}}$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.