0
$\begingroup$

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

  • 1
    http://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$.2012-10-05

1 Answers 1

1

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.