How many fix point free permutations of 5 elements are there?

Question

I am trying to find out how many fix point free permutations of 5 elements there are. A permutation is fix point free, if $\pi (i) \neq i$. I am trying to solve this problem using the inclusion exclusion principle but I really have no idea how to approach this problem. I hope somebody can help.

Answer 1

IE Principle:

• Include the number of combinations with at least $\color\red0$ digits at the right place: $\binom{5}{\color\red0}\cdot(5-\color\red0)!$
• Exclude the number of combinations with at least $\color\red1$ digits at the right place: $\binom{5}{\color\red1}\cdot(5-\color\red1)!$
• Include the number of combinations with at least $\color\red2$ digits at the right place: $\binom{5}{\color\red2}\cdot(5-\color\red2)!$
• Exclude the number of combinations with at least $\color\red3$ digits at the right place: $\binom{5}{\color\red3}\cdot(5-\color\red3)!$
• Include the number of combinations with at least $\color\red4$ digits at the right place: $\binom{5}{\color\red4}\cdot(5-\color\red4)!$
• Exclude the number of combinations with at least $\color\red5$ digits at the right place: $\binom{5}{\color\red5}\cdot(5-\color\red5)!$

---

The answer is therefore $\sum\limits_{n=0}^{5}(-1)^{n}\cdot\binom{5}{n}\cdot(5-n)!=44$

Answer 2

Method $3$ from this answer shows how to compute Derangements using Inclusion-Exclusion.

The answer to this question is $$ \begin{align} \mathcal{D}(5) &=\sum_{k=0}^5(-1)^k\frac{5!}{k!}\\ &=120-120+60-20+5-1\\[9pt] &=44 \end{align} $$ which is the closest integer to $\dfrac{5!}e$.

Answer 3

Using the inclusion-exclusion principle states:

$|\bigcup\limits_{i=1}^{n}A_{i}| = \sum\limits_{\phi \neq J \subseteq\{1,2,...,n\}}^{} (-1)^{|J| - 1}|\bigcap\limits_{j \in J}A_j|$

Setting $A_i$ as the set of all permutations in $S_n$ which fix $i$, then $\bigcup\limits_{i=1}^{n}A_{i}$ becomes the set of all permutations that have a fixed point. Then the number of fixed-point-free permutations on in $S_n$ is simply:

$|S_n| - |\bigcup\limits_{i=1}^{n}A_{i}|$

But it is easily noticed that if $\phi \neq J\subseteq \{1,2,...,n\}$, that

$|\bigcap\limits_{j \in J}A_j| = (n - |J|)!$

also the number of subsets of $\{1,2,...,n\}$ of a fixed size $k$, is well known to be ${n}\choose {k}$.

Using this one obtains:

$\sum\limits_{\phi \neq J \subseteq\{1,2,...,n\}}^{} (-1)^{|J| - 1}|\bigcap\limits_{j \in J}A_j| = \sum\limits_{k = 1}^{n}(-1)^{k-1} \binom{n}{k}(n - k)!$

Therefore, the number of fixed-point free permutations on an n-element set is:

$n! - \sum\limits_{k = 1}^{n}(-1)^{k-1} \binom{n}{k}(n - k)! = \sum\limits_{k = 0}^{n}(-1)^k\frac{n!}{k!}$

Remark: The ratio of fixed-point-free permutations, to the number of permutations is: $\frac{\sum\limits_{k = 0}^{n}(-1)^k\frac{n!}{k!}}{n!} = \sum\limits_{k = 0}^{n}(-1)^k\frac{1}{k!} \approx \frac{1}{e}$ - which is quite interesting