This problem was inspired by this James Randi challenge.

Given $12$ numbered ($1$ to $12$) pigeonholes and $12$ numbered balls (also from $1$ to $12$); what is the probability that a random permutation would leave no balls in its corresponding hole?

Let $a_n$ be the set of permutations of numbers $1$ through $n$ such that for all $1\leq i \leq n$, $perm[i] \neq i$. Clearly $a_1 = 0$ and $a_2 = 1$. I noticed that the following recurrence relation: $$ a_n = (n - 1) (a_{n-1} + a_{n-2}) $$

was successful at predicting $a_n$ for $n = 3, \ldots, 12$. I wish to understand the following:

  1. The justification for the recurrence relationship. My idea was the following: For the first hole, there is a total of $(n-1)$ possibilities. After one such number has been picked, we go to the index $i$ corresponding to this number. In case the $i$th hole points back to the first hole, this means the total number of possibilities is given by $a_{n-2}$. If it does not, the total number of possibilities will be given by $a_{n-1}$. This isn't quite satisfactory as there is also the possibility that $i$ points to hole $j$ and $j$ points back to the first hole.

  2. I noticed that the probability $a_n/n!$ tends to $1/e \approx 0.3678794\ldots$ when n tends to infinity. What is the reason for this?

  3. Is there a way to solve this recurrence relationship such that I can obtain $a_n$ without calculating every $a_i,i<n$?


marked as duplicate by almagest, hardmath, AlexR, joriki probability May 16 '16 at 19:19

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.