2
$\begingroup$

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 !

$\endgroup$
2
$\begingroup$

Suppose we want a permutation where we fix exactly $K$ of the $N$ numbers. There are two things we must do:

  1. Choose which $K$ numbers should be in their own positions.
  2. 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!}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.