# Probability of placement in a random ordering of integers (inclusion-exclusion rule)

Problem

Let $a_1, ..., a_n$ be a random ordering of integers $1,...,n$.

What is the probability that there exists no $1 \leq i \leq n$ such that $a_i = i$?

Attempted solution

For #1: let $A_i = \{$ the event that $a_i \neq i \}$. We want $P(A_1 \cap ... \cap A_n)$.

$P(A_1 \cap ... \cap A_n)$

$= 1 - P(A_1^c \cup ... \cup A_n^c)$ by complement rule

$= 1 - \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 \leq ... \leq i_k \leq n} P(A_{i_1}^c \cap ... \cap A_{i_k}^c )$ by inclusion-exclusion formula

Then, $P(A_{i_1}^c \cap ... \cap A_{i_k}^c ) = P(a_{i_1} = i_1, ..., a_{i_k} = i_k) = \frac{(n-k)!}{n!}$

I'm fairly confident this is correct up to here. However, I'm not sure where to go with this. How can I reduce the nasty summation from the inclusion-exclusion formula?

$\sum_{1 \leq i_1 \leq ... \leq i_k \leq n} \frac{(n-k)!}{n!}$

• One cannot. However, already for $n$ of quite modest size, the answer is extremely close to a very recognizable number. For details please see Derangements in Wikipedia. Commented Apr 9, 2015 at 15:18
• Thanks André. Yea, I keep thinking that it must somehow be related to $e$ as $n \to \infty$ (or rather $e-1$, I think?), but can't figure out why. And from what I've been told, it is possible to somehow simplify this problem further I think. Commented Apr 9, 2015 at 15:24
• Yes, it is possible to simplify quite a bit. For any particular $k$, there are $\binom{n}{k}$ terms in the sum, so the sum for $k$ simplifies to $\pm \frac{1}{k!}$ Commented Apr 9, 2015 at 15:27

I prefer writing this formula of inclusion exclusion as follow (but you can write it as you like just replace $i_1\leq i_2$ to a strict inequality): $$P(A_1\cap A_2\cap \cdots A_n)=\sum_{I\subset[1,n]} (-1)^{|I|}P\left(\bigcap_{i\in I} A_i\right)\tag1$$
and as you proved: $$P\left(\bigcap_{i\in I} A_i\right)=\frac{(n-|I|)!}{n!}\tag2$$
and this implies that: $$P(A_1\cap A_2\cap \cdots A_n)=\sum_{I\subset[1,n]} (-1)^{|I|}\frac{(n-|I|)!}{n!}\tag3$$
Now we want to change the sum, we want to run over the value of the cardinal: \begin{align}P(A_1\cap A_2\cap \cdots A_n)&=\sum_{I\subset[1,n]} (-1)^{|I|}\frac{(n-|I|)!}{n!}\tag4\\ &=\sum_{k=0}^n\sum_{I\subset[1,n],\ |I|=k} (-1)^{|I|}\frac{(n-|I|)!}{n!}\tag{5}\\ &=\sum_{k=0}^n(-1)^{k}\frac{(n-k)!}{n!}\sum_{I\subset[1,n],\ |I|=k}1 \tag{6} \\&=\sum_{k=0}^n(-1)^{k}\frac{(n-k)!}{n!}\dbinom{n}{k} \tag{7}\\ &=\sum_{k=0}^n\frac{(-1)^{k}}{k!}\tag8\end{align}
• In $(1)$ the sum run over all subsets of $[1,n]$ and it's the same thing you wrote because you take a strictly increasing sequence of integers and this is equivalent to taking a subset of $[1,n]$
• $(5)$ to $(6)$ because the value of the formula does not depend on $I$ because the cardinal was fixed
• $(6)$ to $(7)$ because there is exactly $\dbinom{n}{k}$ subsets $I$ of cardinal $k$