Question

In how many ways can all of the letters be placed in the wrong envelopes? 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?

Answer 1

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're 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=1854Or we can use formula 
7! * ( 1/2! - 1/3! + 1/4! - 1/5! + 1/6! - 1/7! ) 
= 2520 - 840 + 210 - 42 + 7 - 1
= 1854