3
$\begingroup$

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.

  • 3
    Look up "derangements".2012-11-22
  • 0
    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.2012-11-22
  • 0
    Yes, only one ball goes in each box.2012-11-22
  • 1
    Look at [this.](http://en.wikipedia.org/wiki/Derangement) 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$.2012-11-22
  • 0
    Previously on derangements: http://math.stackexchange.com/questions/14666/number-of-permutations-where-n-position-n2012-11-22

2 Answers 2

2

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

2

In Python:

round(math.factorial(n) / math.e) / math.factorial(n) 
  • 0
    The `math` module has a `factorial` function handily available.2012-11-22
  • 0
    @AlexGaynor edited2012-11-22