Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
this might be useful –  Patrick Li Oct 5 '12 at 11:46
1  
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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.