Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

There are 220 people and 35 boxes filled with trinkets.

Each person takes one trinket out of a random box.

What is the probability that the 220 people will have grabbed a trinket from exactly 12 different boxes?

I'm trying to calculate the probability of grabbing a trinket from at most 12 boxes, $P(12)$. Then calculate $P(11)$ with the answer being $P(12)-P(11)$ but I'm drawing blank.
$P(12) = 1-(23/35)^{220}$ doesn't look right to me.

share|cite|improve this question
Very few discrete probability calculations result in a cumulative probability, like $P(X\leq C)$. – rschwieb Jun 1 '12 at 11:56
@rschwieb How does this affect my problem? – Captain Giraffe Jun 1 '12 at 12:08
I'm still working on an explanation. I just mean that it looks like you're treating all probability computations as if they were cumulative. It also looks like you (arbitrarily) attempted a binomial probability computation, when the givens don't resemble a simple binomial experiment. It's a bit more complex than that, I think :) I could be (and probably am) wrong about your intentions, but I just wanted to alert you to habits you might not have realized you were exercising. – rschwieb Jun 1 '12 at 12:20
@rschwieb I see, and you are correct in your assumption of my previous attempt. – Captain Giraffe Jun 1 '12 at 12:21
up vote 2 down vote accepted

If the probability that the first $n$ people have chosen from exactly $c$ boxes out of a possible $t$ total boxes [$t=35$ in this case] is $p(n,c,t)$ then $$p(n,c,t)=\frac{c \times p(n-1,c,t)+(t-c+1)\times p(n-1,c-1,t)}{t}$$ starting with $p(0,c,t)=0$ and $p(n,0,t)=0$ except $p(0,0,t)=1$.

Using this gives $p(220,12,35) \approx 4.42899922 \times 10^{-94}$. This is close to but not exactly the naive ${35 \choose 12}\times \left(\frac{12}{35}\right)^{220} \approx 4.42899948\times 10^{-94}$.

share|cite|improve this answer
This is most likely what I want. Now, how do I understand this? In particular I did identify a recurrence relation when thinking about it, but I don't know how to solve it. Nor can I see what you are doing. – Captain Giraffe Jun 1 '12 at 23:21
The probability the first $n$ have chosen from $c$ boxes is the probability the first $n-1$ have chosen from $c$ boxes times the probability the $n$th chooses from one of the $c$ plus the probability the first $n-1$ have chosen from $c-1$ boxes times the probability the $n$th chooses from one of the rest. – Henry Jun 2 '12 at 6:42

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.