Problems on Derangements - Combinatorics

Question

Determine the number of permutations of $ 1,2, \ldots ,8$ in which no even integer is in its natural position. Please solve this using concept of derangements.

Answer 1

Let $S$ be the set of all permutations of $\{1, 2, . . . , 8\}$. Let $A_1$ be the set of all permutations in $S$ which has $2$ in it natural position; $A_2$ be the set of all permutations in $S$ which has $4$ in it natural position; $A_3$ be the set of all permutations in $S$ which has $6$ in it natural position and $A_4$ be the set of all permutations in $S$ which has $8$ in it natural position. Then

$|A_1| = |A_2| = |A_3| = |A_4| = (8 − 1)!$,

$|A_1 ∩ A_2| = |A_1 ∩ A_3| = |A_1 ∩ A_4| = |A_2 ∩ A_3| = |A_2 ∩ A_4| = |A_3 ∩ A_4| = (8 − 2)!$,

$|A_1 ∩ A_2 ∩ A_3| = |A_1 ∩ A_2 ∩ A_4| = |A_1 ∩ A_3 ∩ A_4| = |A_2 ∩ A_3 ∩ A_4| = (8 − 3)!$,

$|A_1 ∩ A_2 ∩ A_3 ∩ A_4| = (8 − 4)!$. Then the set of permutations of $\{1, 2, . . . , 8\}$ in which no even integers are in their national positions is $\bar A_1 ∩ \bar A_2 ∩ \bar A_3 ∩ \bar A_4 $ and the number of the elements is $8! − 4 · 7! + 6 · 6! − 4 · 5! + 4! = 24024. $ $\blacksquare$

(And also we can use this identity which is related to derangement : $n! = \Sigma _{k=0}^n \binom {n}{k}D_{n-k}= \Sigma _{k=0}^n \binom {n}{k}D_{k}.$

Proof: Let $S$ be the set of all permutations of $\{1, 2, . . . , n\}$. Let $A_k$ be the set of all permutations that $k$ integers are fixed at their positions. Then $|S|= n!$ and $|A_k| = \binom{n}{k}D_{n-k}$ . The identity follows from the disjoint union $S = \cup^{n}_{k=0} A_k.$)

Answer 2

The total number of permutations of 1-8 is $8!$. Of these $7!$ fix any one given even number, $6!$ fix two, $5!$ fix three and $4!$ fix all four. So by inclusion-exclusion the number fixing none is $8!-4\cdot7!+6\cdot6!-4\cdot5!+4!=24024$.