1

For a permutation $\sigma = (\sigma_1,...,\sigma_n)$ of the numbers $\{1,...,n\}$ a deranged index is an $i$ such that $\sigma_i \neq i$. We know how to count deranged permutations (permutations that $\forall 1\leq i \leq n : \sigma_i \neq i$) and it is given by $!n = n! \sum_{i=0}^{n} {\frac{(-1)^i}{i!}}$.

However, I am interested, given an integer $1 \leq k \leq n$, in counting how many permutations exist that have $k$ deranged indices. How do I go about this? I started reasoning by saying that $k$ can never be equal to $1$ since if we want a deranged index we must swap the according number with some other number and then that number as well is not in its place. But I am not sure I can generalize that for any odd $k$ no such derangement exists, and from there I got stuck in my reasoning.

TheNotMe
  • 4,841

1 Answers1

5

For a given $k$ you can just count the number of ways to choose the $n-k$fixed elements and multiply by the number of ways to derange the rest, so it is ${n \choose n-k}(!k)$ The fact that there are none with $k=1$ comes from the fact that there are no derangements of one item.

Ross Millikan
  • 374,822