Number of permutations of $n$ numbers 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 ! 
 A: Suppose we want a permutation where we fix exactly $K$ of the $N$ numbers.  There are two things we must do:


*

*Choose which $K$ numbers should be in their own positions.

*Choose positions for the remaining numbers.


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!}. $$
