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

Question

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!}$

Answer 1

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$