Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
this might be useful – Patrick Li Oct 5 '12 at 11:46
1 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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.