2
$\begingroup$

I have one problem which goes like this: "In how many ways can $10$ letters be placed in $10$ addressed envelope such that exactly $9$ letters are in correct envelope?"

If I understand the problem correctly this is similar to counting derangement with exactly $r$ matches,I don't know how to do it,please help.

  • 7
    Zero? The tenth letter should go into the correct envelope as well.2011-08-30
  • 0
    I don't have the answer/solution for this one.2011-08-30
  • 4
    There is less to this problem than meets the eye.2011-08-30
  • 0
    @André Nicolas:Pardon,what exactly do you mean?2011-08-30
  • 0
    possible duplicate of [How many fixed points in a permutation](http://math.stackexchange.com/questions/22537/how-many-fixed-points-in-a-permutation)2011-08-30
  • 0
    @Tretwick , André probably wants you to think about what exactly the question is asking more deeply. If 9 letters are in the correct envelope, how many letters are in incorrect envelopes?2011-08-30
  • 0
    Related: http://math.stackexchange.com/questions/17320/derivation-of-the-partial-derangement-rencontres-numbers-formula2011-08-30
  • 0
    @Aryabhata I thought so too, but this question is more like a puzzle :-)2011-08-30
  • 0
    @Srivatsan: I was going by the title and was addressing the general question.2011-08-30
  • 0
    It has already been solved by @Srivatsan Narayanan. Can exactly $9$ be in the right envelope? No, because there is only one letter left over, and the right envelope for that letter.2011-08-30
  • 0
    Something less abstract than envelopes and letters. Ten married couples. All $20$ people are dancing, in pairs. Could *exactly* $9$ women be dancing with their husbands? Who is left over for the $10$th woman to dance with?2011-08-30

1 Answers 1

6

If nine letters go into the correct envelopes, what can you say about the remaining 1 letter?

The following is not necessary for solving this problem, but I am adding it since you mentioned derangements and number of permutations with exactly $k$ matches (aka fixed points). The more general problem is to find the number of permutations with exactly $k$ fixed points. The solution for this is described in this wikipedia page.

  • 1
    It has to go the correct envelope.2011-08-30
  • 0
    Yes. So, the answer is...2011-08-30
  • 0
    $0$,thanks a lot for your inputs :-)2011-08-30