# Arrangement of numbers using exclusion-inclusion principle

Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate the number of arrangement of first N natural numbers, where in first M positions; exactly K numbers are in their initial position.

For Example, N = 5, M = 3, K = 2

You should count this arrangement {1, 4, 3, 2, 5}, here in first 3 positions 1 is in 1st position and 3 in 3rd position. So exactly 2 of its first 3 are in there initial position.

But you should not count {1, 2, 3, 4, 5}. What is the result if N=10,M=6,K=3? And how will I find out the result for any N,M,and K?

we'll find the number of permutation in which we have exactly $k$ of the first $m$ in their initial position. Define $P_j =$ the $j$-th number is in its initial place, where $j$ is between $1$ and $m$
$W(r) = $$m\choose r$$(n-r)!$
And then by inclusion-exclusion, if we want exactly $k$ out of $m$ to satisfy we have:
$E(m)=\sum_{r=k}^m (-1)^{r-k} {r\choose k} W(r)$
The set is: $$1,2,3,4\ldots,N$$ now we need first K numbers out of first K positions in their original place: $$\underbrace{1,2,3,\ldots,K}_{M\text{ out of these}},K+1,\ldots,N$$ Selecting M out of this is: $$\binom KM$$ Deranging every other(see derangement formula on mathworld and wikipedia): $$!(N-M)=(N-M)!\sum_{i=1}^{N-M}\frac{(-1)^i}{i!}$$ So total: $$P=\binom KM(N-M)!\sum_{i=1}^{N-M}\frac{(-1)^i}{i!}\equiv\;!(N-M)\binom KM$$