4
$\begingroup$

How many permutations of $\{1,2, \dots , n\}$ derange the odd numbers? I have the answer in my text book but I don't know how they got it.

1 Answers 1

3

In other words, if $\pi$ is the permutation you want $\pi(n) \ne n$ for all odd $n$.
You can do this using inclusion-exclusion. For any subset $A \subseteq \{1,2,\ldots n\}$, let $f(A)$ be the number of permutations $\pi$ such that $\pi(n) = n$ for $n \in A$ (and possibly others). Obviously $f(A) = (n - |A|)!$. Let $B$ be any subset of $\{1,\ldots,n\}$. Then inclusion-exclusion says that the number of permutations of $\{1,2,\ldots n\}$ with at least one fixed point in $B$ is the sum of $(-1)^{|A|-1} f(A)$ over all subsets $A$ of $B$, that is, $\displaystyle \sum_{k=1}^{|B|} (-1)^{k-1} (n-k)! {|B| \choose k}$. Subtract this from $n!$ to get the number of permutations with no fixed point in $B$.

See also https://oeis.org/A161131