7
$\begingroup$

$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?

$\endgroup$
  • 4
    $\begingroup$ It is not possible for exactly one letter to be in the wrong envelope. If letter A is in envelope B, then letter B must also be in the wrong envelope. $\endgroup$ – saulspatz Aug 28 '18 at 7:12
6
$\begingroup$

You've gotten confused about the derangements. As I said in a comment, there is no way for there to be exactly one letter in the wrong envelope. What about the case of two letter in the wrong envelope? The remaining eight letters are placed in the correct envelope, so we are concerned with the number of derangements of the two wrongly-place letters. That is we have $${10\choose2}\cdot D_2=45$$ ways for this case. Do same for the case where exactly $3$ letters are not in correct position.

$\endgroup$
  • $\begingroup$ What about case $3$ ? $\endgroup$ – tarit goswami Aug 28 '18 at 7:26
  • $\begingroup$ @taritgoswami Do it the same way. How many ways are there to pick the letters that go in the wrong envelopes? How many derangements of $3$ items are there? $\endgroup$ – saulspatz Aug 28 '18 at 7:28
  • $\begingroup$ Ok, I thought you are saying 45 as the final answer. $\endgroup$ – tarit goswami Aug 28 '18 at 7:29
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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