What are the total number of ways to arrange $N$ objects such that first $K$ are deranged? That is, how many permutations of $N$ objects do not fix the first $K$?
I know the general formula for the derangement of $N$ objects. Is there any way the above problem be reduced to this one?
On
I do not think that there is any way to reduce this to the general case. On can use the standard argument to get a recurrence as follows:
Let $D(n, k)$ be the number of ways of distributing $n$ hats among $n$ heads such that none of the first $k$ heads receives its own hat. As a base cases we know that $D(n, 0) = n!$ and $D(n, 1) = (n-1) (n-1)!$. For $k>1$ the first head can get any of $n-1$ hats, let $n-1$ get hat $i$. There are three cases to consider:
1) Head $i$ does not get hat 1. This means that each of the next $k-1$ heads has precisely one hat that it cannot get, so there are a total of $(n-1)D(n-1, k-1)$ permutations in this case.
2) Head $i$ gets hat 1 and $i\le k$. This means that there are $n-2$ remaining heads, and $k-2$ heads that need to get a different hat. There are $(k-1)D(n-2,k-2)$ permutations in this case.
3) Head $i$ gets hat 1 and $i > k$. This means that there are $n-2$ remaining heads, and $k-1$ heads that need to get a different hat. There are $(n-k)D(n-2,k-1)$ permutations.
Putting it all together, we get. $$D(n,k) = (n-1)D(n-1,k-1) + (k-1)D(n-2,k-2) + (n-k)D(n-2,k-1)$$ for $k>1$. This recurrence does not seem to have a nice solution (I may be missing something).
A decent first approximation is $$D(n,k) \approx \frac{n-k}{n-k+1}n!$$ for large enough $n$.
Let $S$ be the set of all permutations of the $N$ objects, and let $E_{i}$ be the set of permutations which fix the element $i$, for $1\le i\le k$.
Then
$$\left\vert \overline{E_{1}}\cap\cdots\cap\overline{E_{n}}\right\vert=\vert S\vert-\sum_{i}\vert E_{i}\vert+\sum_{i<j}\vert E_{i}\cap E_{j}\vert-\cdots $$
$$=N!-\binom{k}{1}(N-1)!+\binom{k}{2}(N-2)!-\cdots+(-1)^k\binom{k}{k}(N-k)!.$$