3
$\begingroup$

Possible Duplicate:
Number of permutations where n ≠ position n

In how many ways can 5 messages be posted in 5 envelopes so that no correct message is posted, if each envelope only has one correct message from the 5, and each message only has one correct envelope?

Possible notation: We represent each envelope by an upper-case letter, $A, B, C, D, E$, and each message by a lower-case letter, $a,b,c,d,e$, and denote the positioning of the messages in envelopes as $A_x B_xC_x D_x E_x~$, such that a possible envelope-message configuration might be $A_c B_d C_b D_e E_a~$, with message $c$ being slotted in envelope $A$ and message $d$ being slotted in envelope $B$ etc. The correct message for envelope $A$ is message $a$ etc.

I have a potential solution to this problem, but I'm wondering if there are some alternate, simpler solutions.

  • 0
    Take a look at the counting formulas [here](http://en.wikipedia.org/wiki/Derangement); the recursive formula is especially easy to use when $n$ is small, as it is here. (Make sure that you get the right initial conditions.)2011-09-29
  • 3
    You're looking for $!5$; see [Wikipedia](http://en.wikipedia.org/wiki/Derangement) or [MathWorld](http://mathworld.wolfram.com/Derangement.html) on what's termed '*derangements*.' This is arguably a duplicate of [this question](http://math.stackexchange.com/questions/14666/number-of-permutations-where-n-position-n), and you might also want to see [this question](http://math.stackexchange.com/questions/14477/proof-of-subfactorial-formula-n-n-sum-i-1n-n-choose-i-quadn) or various others like it.2011-09-29
  • 1
    There is, as the links show, a lot of material on this, of a general character. But for $5$ envelopes, all one needs is patience and carefulness, though a small idea saves quite a bit of time. Letter $a$ goes into one of $B$, $C$, $D$, $E$. By symmetry the number of "good" permutations is $4$ times the number of good permutations that send $a$ to $B$. Now just make a complete list of the good permutations that send $a$ to $B$. Hint: they are of two types (i) $b$ is sent to $A$ and (ii) $b$ is sent somewhere else. It should not take more than a few minutes.2011-09-29

0 Answers 0