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

This question already has an answer here:

You have n balls, and n boxes. There is a pairing of each ball to a box (and vice versa). If you were to randomly place balls in boxes, what is the probability that none of the balls would go in "their" box?

I've solved this numerically for:

n | probability
1 | 0
2 | 1 / 2
3 | 1 / 3

I believe an analytic solution is possible, but I've yet to be able to formulate it.

share|cite|improve this question

marked as duplicate by Marc van Leeuwen, Carl Mummert, SHOBHIT GAUTAM, ᴡᴏʀᴅs, Jack D'Aurizio Feb 22 '15 at 15:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Look up "derangements". – mjqxxxx Nov 22 '12 at 5:53
When you randomly place balls in boxes, are you careful to put only one ball in each box? If so, you are talking about the classical problems of derangements, about which there is a copious literature. – Gerry Myerson Nov 22 '12 at 5:53
Yes, only one ball goes in each box. – Alex Gaynor Nov 22 '12 at 5:54
Look at this. Whether there is a closed form formula depends on what you call closed form. But there is a very nice formula. And it turns out the probability approaches $1/e$. – André Nicolas Nov 22 '12 at 5:55
Previously on derangements:… – Rahul Nov 22 '12 at 18:18
up vote 2 down vote accepted

This is the number of derangements of $n$ items divided by $n!$ (the number of arrangements of $n$ items). See this answer for a number of proofs of the ways to count the number of derangements of $n$ items.

The probability is $$ \sum_{k=0}^n\frac{(-1)^k}{k!} $$ As James Tauber has said, for $n\ge1$, this is $$ \frac{\mathcal{D}(n)}{n!}=\frac{\left\lfloor\dfrac{n!}{e}+\dfrac12\right\rfloor}{n!} $$ This fails for $n=0$, where the probability is $1$.

share|cite|improve this answer

In Python:

round(math.factorial(n) / math.e) / math.factorial(n)
share|cite|improve this answer
The math module has a factorial function handily available. – Alex Gaynor Nov 22 '12 at 6:17
@AlexGaynor edited – James Tauber Nov 22 '12 at 16:29

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