A correspondent writes 7 letters and addresses 7 envelopes, one for each letter. In how many ways can all of the letters be placed in the wrong envelopes?

+4 votes

A correspondent writes 7 letters and addresses 7 envelopes, one for each letter. In how many ways can all of the letters be placed in the wrong envelopes?

+2 votes

Answer: 1854

1 letter, 0 way

2 letters, 1 way

3 letters, 2 ways

4 letters: 9 Ways 3*2=6 ways of cycling the 4 around, but then 3 ways of doing 2+2. (=9)

So partitioning is the way to go. A partition of 1 always maps the letter into the right envelope, so there's no answers with partition 1.

7 can be

a "cycle" of 7: with 1 case, which has 6*5*4*3*2 permutations

a "cycle" of 5 plus a "cycle" of 2: with 7*6/2 cases and 4*3*2 permutations

a "cycle" of 4 plus a "cycle" of 3: 7*6*5/6 cases and (2 {for the 3} * 9 {for the 4}) permutations

i.e. 720+504+630=1854

Or we can use formula

7! * ( 1/2! - 1/3! + 1/4! - 1/5! + 1/6! - 1/7! )

= 2520 - 840 + 210 - 42 + 7 - 1

= 1854

+1 vote

```
E1 E2 E3 E4 E5 E6 E7
L1 L2 L3 L4 L5 L6 L7
```

Now assume L1 can be put into 7 ways into an envelope and only one is correct and 6 are wrong ways similarly for L2 there are six ways and so on

So total possible wrong ways are 6*6*6*6*6*6*6

=) 6^7 or 279936

...