# misaddressed letters problem

I'm trying to solve the misaddressed letters problem (number of permutations on $\{1,...,n\}$ such that $k$ is not in the $k$-th place) in the following way and something should be wrong: total number of permutations: $n!$ now I want to substract:

permutations with exactly one correct place: $n (n-2)!$

permutations with exactly two correct places: ${n \choose 2} (n-3)!$

... permutations with exactly s correct places: ${n \choose s} (n-(s+1))!$

What am I missing? thanks

-
this might be useful –  Patrick Li Oct 5 '12 at 11:46
en.wikipedia.org/wiki/Derangement. Also note that the formula for exactly one entry in the right place is not $n(n-2)!$, it is $n$ times the number of derangements of $n-1$; for instance for $n=2$ it is $0$ since for $n=1$ there are no derangements, whereas $2\times0!=2$. –  Marc van Leeuwen Oct 5 '12 at 11:58

You’re off by one in each of your second factors. Let $K\subseteq\{1,\dots,n\}$ with $|K|=k$; the permutations that leave every element of $K$ in its proper place can permute $\{1,\dots,n\}\setminus K$ arbitrarily, so there are $(n-k)!$ of them. Thus, as $K$ runs over all $k$-subsets of $\{1,\dots,n\}$, we get $\binom{n}k(n-k)!$ permutations, not $\binom{n}k(n-(k+1))!$.
Now it should work: there are $$\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)!$$ permutations that have at least one fixed point, and you need only subtract from $n!$ to get the number of derangements.