What is the number of permutations of the first $N$ natural numbers such that for exactly $K \leq N$ of the numbers the following condition is true:
- Number $x$ is in position $x$ in the permutation
Example : if $N = 3$, the numbers are $1,2,3$
Permutations $132$,$213$,$321$ have only $1$ element each in required position.
So, for $K=1$ and $N=3$, the required number of permutations is $3$.
I tried using exclusion-inclusion principle, but I was able to find an answer only for $K=1$. For larger values of $K$, it is becoming too cumbersome. Please help !
Best Answer
Suppose we want a permutation where we fix exactly $K$ of the $N$ numbers. There are two things we must do:
For the first step, note that there are $\binom{N}{K}$ ways to choose the $K$ numbers that will be in their own positions. Once we have chosen them, we can fix their positions, and only worry about the rest.
That leaves us with $N-K$ numbers to permute in the second step. However, since we already have $K$ elements in their own positions, we cannot put any of these $N-K$ numbers in their own position as well. Such a permutation is called a derangement. If the number of derangements of $m$ elements is $D_m$, then there are $D_{N-K}$ choices for the second step.
Putting it all together, this would give us an answer of $\binom{N}{K} D_{N-K}$.
Now how do we find $D_m$? You can compute this using the Inclusion-Exclusion principle (it is perhaps a bit simpler now that we don't have to worry about the $K$ elements in their own positions). Recall that we have $m$ elements, and we want to count how many permutations do not put any element in their own position. Let $P_i$ be the set of permutations that puts the $i$th element in its own position. A deerangement is then a permutation that is not in any set $P_i$. By Inclusion-Exclusion, we have $$ D_m = \left| \left( \cup_i P_i \right)^c \right| = \sum_{\ell = 0}^m \sum_{I \in \binom{[m]}{\ell} } (-1)^{\ell} \left| \cap_{i \in I} P_i \right|. $$
In the summand on the right-hand side, we count the number of permutations that fix a subset $I \subset [m]$ of the elements. Note that if we fix $\ell$ elements, we are free to permute the rest, so there are $(m - \ell)!$ such permutations. This gives \begin{align} D_m &= \sum_{\ell = 0}^m \sum_{I \in \binom{[m]}{\ell}} (-1)^{\ell} (m- \ell)! \\ &= \sum_{\ell = 0}^m (-1)^{\ell} \binom{m}{\ell} (m-\ell)! \\ &= \left( \sum_{\ell = 0}^m \frac{(-1)^{\ell}}{\ell!} \right) m!. \end{align}
Note that the sum converges to $e^{-1}$ as $m \rightarrow \infty$, which means the number of derangements is asymptotically $m!/e$ as $m$ grows.
Finally, if we wanted to, we could plug this sum back into our formula for the number of permutations of $N$ numbers with exactly $K$ fixed points to get $$ \binom{N}{K} \left( \sum_{\ell = 0}^{N-K} \frac{(-1)^{\ell}}{\ell!} \right) (N-K)! = \left( \sum_{\ell = 0}^{N-K} \frac{(-1)^{\ell}}{\ell!} \right) \frac{N!}{K!}. $$