Derangement of $n$ elements 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?
 A: 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)!.$$
A: 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$.
