<center> <img src = "https://i.imgsafe.org/a9/a90893bfe3.png"/></center>
[1]
## 0. What is a Derangement?

In mathematics, __permutation__  is an act of arranging all the members of a set into some sequence or order. A permutation which leaves no element fixed is called a __derangement__ . In many cases, we deal with <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> items (a finite set), each labeled as 

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;n&space;\right\}" title="\left\{ 1, 2, ..., n \right\}" /> </center> 

So, put another way, a derangement of <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> objects is a permutation of them without fixed points. The number of derangements of <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> obejcts is usually written as <img src="http://latex.codecogs.com/gif.latex?D_n" title="D_n" align = "center"/> . 

For example, <img src="http://latex.codecogs.com/gif.latex?D_1&space;=&space;0" title="D_1 = 0" align = "center"/>, since singleton set can not have any derangements. Also <img src="http://latex.codecogs.com/gif.latex?D_2&space;=&space;1" title="D_2 = 1" align = "center"/>, because only derangement is assigning 

<center> <img src="http://latex.codecogs.com/gif.latex?1&space;\mapsto&space;2,\&space;2&space;\mapsto&space;1" title="1 \mapsto 2,\ 2 \mapsto 1" /> </center>

Let's look at one more example <img src="http://latex.codecogs.com/gif.latex?D_3" title="D_3" align = "center"/> . There are total 2 derangements, 

|  Element | 1 | 2 | 3 |
|:--------:|:-:|:-:|:-:|
| maps to  | 2 | 3 | 1 |
|  maps to | 3 | 1 | 2 |

In general, we need to ask the question: 

<center> <b><i> Of the <img src="http://latex.codecogs.com/gif.latex?n!" title="n!" /> different permutations of <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> distinct objects, how many leave no object in its original place? </i></b></center>

The answer to the question will provide a general formula for <img src="http://latex.codecogs.com/gif.latex?D_n" title="D_n" align = "center"/> as well as 

<center> <img src="http://latex.codecogs.com/gif.latex?p_n&space;=&space;\frac{D_n}{n!}" title="p_n = \frac{D_n}{n!}" /> </center>

the __probability__ that a permutation of <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> objects is a derangement. 

## 1. Old but Gold Recurrence Relation

Viewing <img src="http://latex.codecogs.com/gif.latex?D_1,&space;D_2,D_3,&space;...,&space;D_n,..." title="D_1, D_2,D_3, ..., D_n,..." align = "center"/> as a sequence <img src="http://latex.codecogs.com/gif.latex?\left\{&space;D_n&space;\right\}" title="\left\{ D_n \right\}" align = "center"/> ,  let's find a recurrence relation for <img src="http://latex.codecogs.com/gif.latex?D_n" title="D_n" align = "center"/> . Since we already know the value of <img src="http://latex.codecogs.com/gif.latex?D_1" title="D_1" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?D_2" title="D_2" align = "center"/> , let's focus on the values of <img src="http://latex.codecogs.com/gif.latex?D_n" title="D_n" align = "center"/> for <img src="http://latex.codecogs.com/gif.latex?n&space;\geq&space;3" title="n \geq 3" align  ="center"/> . 

If a permutation 

<center> <img src="http://latex.codecogs.com/gif.latex?\sigma:&space;\left\{&space;1,&space;2,&space;...,&space;n&space;\right\}&space;\rightarrow&space;\left\{&space;1,&space;2,&space;...,&space;n&space;\right\}" title="\sigma: \left\{ 1, 2, ..., n \right\} \rightarrow \left\{ 1, 2, ..., n \right\}" /> </center>

is a derangement, then it must be that <img src="http://latex.codecogs.com/gif.latex?\sigma(1)&space;\neq&space;1" title="\sigma(1) \neq 1" align = "center"/> , which leaves <img src="http://latex.codecogs.com/gif.latex?n-1" title="n-1" /> possibilities for it. Among those, choose 

<center> <img src="http://latex.codecogs.com/gif.latex?\sigma(1)&space;=&space;k&space;(>&space;1)" title="\sigma(1) = k (> 1)" /> </center>

Now there are two possibilities. 

<b>1. </b> If <img src="http://latex.codecogs.com/gif.latex?\sigma(k)&space;=&space;1" title="\sigma(k) = 1" align = "center"/> ,  this is nothing but derangement of 

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;2,&space;3,&space;...,k-1,&space;k&plus;1,...n&space;\right\}&space;=&space;\left\{&space;1,&space;2,&space;...,&space;n&space;\right\}&space;\setminus&space;\left\{1,k&space;\right\}" title="\left\{ 2, 3, ...,k-1, k+1,...n \right\} = \left\{ 1, 2, ..., n \right\} \setminus \left\{1,k \right\}" /> </center>
and there are exactly <img src="http://latex.codecogs.com/gif.latex?D_{n-2}" title="D_{n-2}" align = "center"/> of these. 

<b> 2. </b> If <img src="http://latex.codecogs.com/gif.latex?\sigma(k)&space;\neq&space;1" title="\sigma(k) \neq 1" align = "center"/>, this is nothing but derangement of 

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;2,&space;3,&space;...,&space;n&space;\right\}" title="\left\{ 2, 3, ..., n \right\}" /> </center>

to 

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;k-1,&space;k&plus;1,&space;...,&space;n&space;\right\}" title="\left\{ 1, 2, ..., k-1, k+1, ..., n \right\}" /> </center>

with a restriction <img src="http://latex.codecogs.com/gif.latex?\sigma(k)&space;\neq&space;1" title="\sigma(k) \neq 1" align = "center"/> . The situation is totally equivalent to derangement of 

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;2,&space;3,&space;...,&space;n&space;\right\}" title="\left\{ 2, 3, ..., n \right\}" /> </center>

to 

<center ><img src="http://latex.codecogs.com/gif.latex?\left\{&space;2,&space;3,&space;...,&space;n&space;\right\}" title="\left\{ 2, 3, ..., n \right\}" /></center>

if  <img src="http://latex.codecogs.com/gif.latex?1" title="1" align=  "center"/> is viewed as <img src="http://latex.codecogs.com/gif.latex?k" title="k" />; so there are exactly <img src="http://latex.codecogs.com/gif.latex?D_{n-1}" title="D_{n-1}" align = "center"/> of these.

Since our choice of <img src="http://latex.codecogs.com/gif.latex?k" title="k" /> was arbitrary, summing all those cases gives 

<center> <img src="http://latex.codecogs.com/gif.latex?D_n&space;=&space;(n-1)(D_{n-1}&space;&plus;&space;D_{n-2})\&space;(n&space;\geq&space;3)" title="D_n = (n-1)(D_{n-1} + D_{n-2})\ (n \geq 3)" /> </center>


---

<center> <b><i> How do we solve this? </i></b> </center>

__Clever trick__ is to divide both sides by <img src="http://latex.codecogs.com/gif.latex?n!" title="n!" /> so that 

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;\frac{D_n}{n!}&space;&=&space;\frac{(n-1)D_{n-1}}{n!}&space;&plus;&space;\frac{(n-1)D_{n-2}}{n!}&space;\\&space;&=&space;\frac{D_{n-1}}{(n-1)!}&space;\left(1-&space;\frac{1}{n}&space;\right&space;)&space;&plus;&space;\frac{D_{n-2}}{(n-2)!}&space;\cdot&space;\frac{1}{n}\\&space;\iff&space;p_n&space;&=&space;\left(1-&space;\frac{1}{n}&space;\right&space;)&space;p_{n-1}&space;&plus;&space;\frac{1}{n}&space;\cdot&space;p_{n-2}&space;\\&space;\iff&space;(p_n&space;&-&space;p_{n-1})&space;=&space;-\frac{1}{n}&space;(p_{n-1}&space;-&space;p_{n-2})&space;\end{align*}" title="\begin{align*} \frac{D_n}{n!} &= \frac{(n-1)D_{n-1}}{n!} + \frac{(n-1)D_{n-2}}{n!} \\ &= \frac{D_{n-1}}{(n-1)!} \left(1- \frac{1}{n} \right ) + \frac{D_{n-2}}{(n-2)!} \cdot \frac{1}{n}\\ \iff p_n &= \left(1- \frac{1}{n} \right ) p_{n-1} + \frac{1}{n} \cdot p_{n-2} \\ \iff (p_n &- p_{n-1}) = -\frac{1}{n} (p_{n-1} - p_{n-2}) \end{align*}" /> </center>

Defining <img src="http://latex.codecogs.com/gif.latex?q_n&space;=&space;p_n&space;-&space;p_{n-1}" title="q_n = p_n - p_{n-1}" align = "center"/> gives 

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;q_n&space;&=&space;\left(&space;-\frac{1}{n}&space;\right&space;)&space;\times&space;\left(&space;-\frac{1}{n-1}&space;\right&space;)&space;\times&space;...&space;\times&space;\left(&space;-\frac{1}{1}&space;\right&space;)&space;\\&space;&=&space;(-1)^{n}&space;\frac{1}{n!}&space;\end{align*}" title="\begin{align*} q_n &= \left( -\frac{1}{n} \right ) \times \left( -\frac{1}{n-1} \right ) \times ... \times \left( -\frac{1}{1} \right ) \\ &= (-1)^{n} \frac{1}{n!} \end{align*}" /> </center>

so that 

<center> <img src="http://latex.codecogs.com/gif.latex?p_n&space;=&space;q_1&space;&plus;&space;...&space;&plus;&space;q_n&space;=&space;\sum_{i=1}^{n}&space;(-1)^{i}\frac{1}{i!}" title="p_n = q_1 + ... + q_n = \sum_{i=1}^{n} (-1)^{i}\frac{1}{i!}" /> </center> 

with 

<center> <img src="http://latex.codecogs.com/gif.latex?D_n&space;=&space;n!&space;\left(&space;\sum_{i=1}^{n}&space;(-1)^{i}\frac{1}{i!}&space;\right)" title="D_n = n! \left( \sum_{i=1}^{n} (-1)^{i}\frac{1}{i!} \right)" /> </center>

---

## 2. The other way around
[2]

We've established the formula for derangement, but there is a more intuitive way of relating the total number of permutations <img src="http://latex.codecogs.com/gif.latex?n!" title="n!" /> with <img src="http://latex.codecogs.com/gif.latex?D_n" title="D_n" align = "center"/> . 

We can count the total <img src="http://latex.codecogs.com/gif.latex?n!" title="n!" /> ways by __partitioning__ the ways into <img src="http://latex.codecogs.com/gif.latex?n&plus;1" title="n+1" align = "center"/> disjoint subsets,  

<center> <img src="http://latex.codecogs.com/gif.latex?T_0,T_1,T_2,...,T_n" title="T_1,T_2,...,T_n" /></center>

where <img src="http://latex.codecogs.com/gif.latex?T_r" title="S_r" align = "center"/> is the set of permutations in which there are exactly <img src="http://latex.codecogs.com/gif.latex?n-r" title="n-r" /> fixed points. If there are <img src="http://latex.codecogs.com/gif.latex?n-r" title="n-r" /> fixed points, we first choose <img src="http://latex.codecogs.com/gif.latex?n-r" title="n-r" /> fixed points among <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> , and arrange leftovers (<img src="http://latex.codecogs.com/gif.latex?r" title="r" /> elements) to have no fixed points. This gives 

<center> <img src="http://latex.codecogs.com/gif.latex?|S_r|&space;=&space;\binom{n}{n-r}D_r&space;=&space;\binom{n}{r}D_r" title="|S_r| = \binom{n}{n-r}D_r = \binom{n}{r}D_r" /> </center>

so that 

---

<center><img src="http://latex.codecogs.com/gif.latex?n!&space;=&space;\sum_{r=0}^{n}&space;\binom{n}{r}&space;D_r" title="n! = \sum_{r=0}^{n} \binom{n}{r} D_r" /> </center>

---

This simple looking relationship is indeed very useful, as we will use in further sections. 

## 3. Expected Number of Fixed points

A rather __paradoxical situation__ arise when we calculate the expeced number of fixed points. Suppose that we perform the experiment of matching the initial arrangement <img src="http://latex.codecogs.com/gif.latex?\left\{&space;1,&space;2,&space;...,&space;n&space;\right\}" title="\left\{ 1, 2, ..., n \right\}" align = "center"/> with a random permutation of itself. Define a random variable <img src="http://latex.codecogs.com/gif.latex?X" title="X" /> as the number of fixed points in single experiment. Then clearly, <img src="http://latex.codecogs.com/gif.latex?X" title="X" /> can have values 

<center> <img src="http://latex.codecogs.com/gif.latex?0,&space;1,&space;2,&space;...,&space;n" title="0, 1, 2, ..., n" /> </center> 

So the expectation is nothing but 

<center> <img src="http://latex.codecogs.com/gif.latex?\mathbb{E}[X]&space;=&space;\sum_{r=0}^{n}&space;r\mathbb{P}(X&space;=&space;r)" title="\mathbb{E}[X] = \sum_{r=0}^{n} r\mathbb{P}(X = r)" /> </center>

In the previous Section, we already obtained the formula for <img src="http://latex.codecogs.com/gif.latex?\mathbb{P}(X&space;=&space;r)" title="\mathbb{P}(X = r)" align = "center"/>, which is

<center> <img src="http://latex.codecogs.com/gif.latex?\mathbb{P}(X&space;=&space;r)&space;=&space;\frac{|T_{n-r}|}{n!}&space;=&space;\frac{\binom{n}{n-r}&space;D_{n-r}}{n!}" title="\mathbb{P}(X = r) = \frac{|T_{n-r}|}{n!} = \frac{\binom{n}{n-r} D_{n-r}}{n!}" /> </center>

Now, straightforward calculation gives 

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;\mathbb{E}[X]&space;&=&space;\sum_{r=0}^{n}&space;r&space;\frac{\binom{n}{n-r}&space;D_{n-r}}{n!}&space;\\&space;&=&space;\sum_{s=0}^{n}&space;(n-s)&space;\frac{\binom{n}{s}D_s}{n!}\&space;(\because&space;s&space;=&space;n-r)&space;\\&space;&=&space;\sum_{s=0}^{n-1}&space;\frac{D_s}{s!(n-s-1)!}\&space;(\because&space;n-n=0)\\&space;&=&space;\frac{1}{(n-1)!}\sum_{s=0}^{n-1}&space;\binom{n-1}{s}D_s&space;\end{align*}" title="\begin{align*} \mathbb{E}[X] &= \sum_{r=0}^{n} r \frac{\binom{n}{n-r} D_{n-r}}{n!} \\ &= \sum_{s=0}^{n} (n-s) \frac{\binom{n}{s}D_s}{n!}\ (\because s = n-r) \\ &= \sum_{s=0}^{n-1} \frac{D_s}{s!(n-s-1)!}\ (\because n-n=0)\\ &= \frac{1}{(n-1)!}\sum_{s=0}^{n-1} \binom{n-1}{s}D_s \end{align*}" /> </center>

Since 

<center> <img src="http://latex.codecogs.com/gif.latex?\sum_{s=0}^{n-1}&space;\binom{n-1}{s}D_s&space;=&space;(n-1)!" title="\sum_{s=0}^{n-1} \binom{n-1}{s}D_s = (n-1)!" /></center>

by our previous result in Section 3, we get 

<center> <img src="http://latex.codecogs.com/gif.latex?\mathbb{E}[X]&space;=&space;1" title="\mathbb{E}[X] = 1" /> </center>

__regardless of__ <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> . 

---

How should we interpret this weird result? Many of us tend to think the expected number of fixed points will grow as <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> increases. However, the probability of making an element <img src="http://latex.codecogs.com/gif.latex?i" title="i" /> as a fixed point is 

<center><b><i> inversely proportional to <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> </i></b></center>

This will help you understand what's going on more clearly. Consider a random variable  <img src="http://latex.codecogs.com/gif.latex?X_i" title="X_i" align = "center"/> such that <img src="http://latex.codecogs.com/gif.latex?X_i&space;=&space;1" title="X_i = 1" align = "center"/> if <img src="http://latex.codecogs.com/gif.latex?i" title="i" /> is a fixed point, and 0 otherwise. Then the expectation of number of fixed points is 

<center> <img src="http://latex.codecogs.com/gif.latex?\sum_{i=1}^{n}&space;\mathbb{P}(X_i&space;=&space;1)&space;=&space;\frac{1}{n}&space;\times&space;n&space;=1" title="\sum_{i=1}^{n} \mathbb{P}(X_i = 1) = \frac{1}{n} \times n =1" /> </center>

so that <img src="http://latex.codecogs.com/gif.latex?1/n,&space;n" title="1/n, n" align = "center"/>  __cancel out__ making the expectation __constant__; 1. 


## 4. Asymptotic Property of derangement
[3]
Finally, one can ask that 

<center> <b><i> What is the asymptotic behavior of <img src="http://latex.codecogs.com/gif.latex?p_n" title="p_n" /> as <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> gets large? </i></b></center>

This is nothing but asking the limit

<center> <img src="http://latex.codecogs.com/gif.latex?p=\lim_{n&space;\rightarrow&space;\infty}&space;p_n&space;=&space;\sum_{i=0}^{\infty}(-1)^i&space;\frac{1}{i!}" title="p=\lim_{n \rightarrow \infty} p_n = \sum_{i=0}^{\infty}(-1)^i \frac{1}{i!}" /> </center>

one can easily show that the limit actually exists, and surprisingly, using the [well known fact](https://en.wikipedia.org/wiki/Taylor_series#Exponential_function) 

<center> <img src="http://latex.codecogs.com/gif.latex?e^{x}&space;=&space;\sum_{i=0}^{\infty}&space;\frac{x^i}{i!}\&space;(\text{for&space;all&space;}&space;x&space;\in&space;\mathbb{R})" title="e^{x} = \sum_{i=0}^{\infty} \frac{x^i}{i!}\ (\text{for all } x \in \mathbb{R})" /> </center>

gives <img src="http://latex.codecogs.com/gif.latex?p&space;=&space;\frac{1}{e}" title="p = \frac{1}{e}" align = "center"/> . 

---

Also one can ask that 

<center><b><i> What is the asymptotic behavior of <img src="http://latex.codecogs.com/gif.latex?&space; \mathbb{P}(X&space;=&space;r)" title="\mathbb{P}(X = r)" align = "center"/> as <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> gets large? </i></b></center>

Recall that we defined random variable <img src="http://latex.codecogs.com/gif.latex?X" title="X" /> as number of fixed points in single random permutation? Using the definition in Section 2 gives 

<center> <img src="http://latex.codecogs.com/gif.latex?\mathbb{P}(X&space;=&space;r)&space;=&space;\frac{\binom{n}{n-r}D_{n-r}}{n!}&space;=&space;\frac{1}{r!}&space;\cdot&space;\frac{D_{n-r}}{(n-r)!}" title="\mathbb{P}(X = r) = \frac{\binom{n}{n-r}D_{n-r}}{n!} = \frac{1}{k!} \cdot \frac{D_{n-r}}{(n-r)!}" /> </center>

We already proved that <img src="http://latex.codecogs.com/gif.latex?\frac{D_{n-r}}{(n-r)!}&space;\rightarrow&space;\frac{1}{e}" title="\frac{D_{n-r}}{(n-r)!} \rightarrow \frac{1}{e}" align = "center" />, so that 

<center><img src="http://latex.codecogs.com/gif.latex?\mathbb{P}_n(X&space;=&space;r)&space;\rightarrow&space;\frac{e^{-1}}{r!}" title="\mathbb{P}_n(X = r) \rightarrow \frac{e^{-1}}{k!}" /></center> 

## 5. Computer Simulation

### 5-1. Expected number of fixed point revisited 

Here is the MATLAB simulation for accumulated expectation of number of fixed points for various <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> . As the number of simulation grows, you can see the accumulated expectation approaches to unity, __regardless of__ <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> . 

<center> <img src = "https://i.imgsafe.org/a7/a7992e91fd.png"/></center>


### 5-2. Asymptotic property of Derangement revisited

Now here is the MATLAB simulation for <img src="http://latex.codecogs.com/gif.latex?p_n" title="p_n" align = "center"/> the probability of having derangement in single permutation. 

<center> <img src = "https://i.imgsafe.org/a8/a8f839b402.png"/></center>

You can see it clearly converges to <img src="http://latex.codecogs.com/gif.latex?1/e" title="1/e" align = "center"/> , oscillating in small region centered <img src="http://latex.codecogs.com/gif.latex?1/e" title="1/e" align = "center"/> . 

## 6. Conclusion
- Number of derangement of <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> items is equal to 
<center> <img src="http://latex.codecogs.com/gif.latex?n!\sum_{r=0}^{n}&space;\frac{(-1)^r}{r!}" title="n!\sum_{r=0}^{n} \frac{(-1)^r}{r!}" /> </center>

- The __expectated number__ of fixed points in single random permutation is 1, __regardless of__ <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> . 

- The probability of having derangement converges to <img src="http://latex.codecogs.com/gif.latex?p_n&space;\rightarrow&space;1/e" title="p_n \rightarrow 1/e" align = "center" /> . 

## 7. Citations
[1] [Image Source Link](https://en.wikipedia.org/wiki/Derangement#/media/File:Derangement4.png), By RokerHRO - Own work, CC BY 3.0

[2] Julian Havil, Nonplussed! Mathematical Proof of Implausible Ideas. Chapter 5 page 53

[3] Julian Havil, Nonplussed! Mathematical Proof of Implausible Ideas. Chapter 5 page 56

---

MATLAB plots are self-made.