$10$ letters are placed in $10$ addressed envelopes. Find how many ways are there such as at most three letters are not in correct envelopes.
My try:
I divided the Problem into $4$ cases:
Case $1.$ If exactly $0$ letters are not in correct envelopes implies that all are in correct envelopes which can be done in $1$ way.
Case $2.$ if Exactly one letter not in its respective envelope , number of ways is
$$ \binom{10}{1} \times \binom{9}{1} \times (D_9+D_8)$$
where $D_n$ is a derangement of length $n$
But for the final two cases, the approach is complicated.
Any better way?
Best Answer
There is exactly one way for all letters to be in their right envelopes.
It's impossible for exactly one letter to be in the wrong envelope, because if letter A is in envelope B, then letter B must also be in the wrong envelope.
For any way of putting exactly two letters in the wrong envelopes, you can get there by having all letters in the correct envelopes, then choose two letters and swap them. Therefore this can happen in $\binom{10}2$ ways.
Finally, for three letters in the wrong envelopes, it's more or less like the above: start with a perfect ordering, choose three letters and then derange them. There are two derangements on three elements, so there are $2\cdot \binom{10}{3}$ ways of doing this.