Inclusion Exclusion Principle?

Question: n letters belong to n envelopes. How many ways can these be arranged such that each letter is in the wrong envelope?

I'm quite stuck. I was thinking of applying the Inclusion-Exclusion Principle, so taking:

(Total combinations = n!) - |A1 u A2 u ... u An|, where Ai is the set where i letters are in the correct envelope.

I'm not sure if that's the correct method, but even if it is, I'm not sure what to write as the final answer?

Thanks for any help :)

Re: Inclusion Exclusion Principle?

I've had this page bookmarked for a while. Still haven't read it. It may give you more help than you want but still..

http://math.ucr.edu/home/baez/qg-win...erangement.pdf

Re: Inclusion Exclusion Principle?

Quote:

Originally Posted by

**combinatorixxx** Question: n letters belong to n envelopes. How many ways can these be arranged such that each letter is in the wrong envelope?

I'm quite stuck. I was thinking of applying the Inclusion-Exclusion Principle, so taking:

(Total combinations = n!) - |A1 u A2 u ... u An|, where Ai is the set where i letters are in the correct envelope.

I'm not sure if that's the correct method, but even if it is, I'm not sure what to write as the final answer?

Thanks for any help :)

See Kenneth Rosen book on Discrete Mathematics and Its Applications,in chapter 6 pg 454 to pg 456

Re: Inclusion Exclusion Principle?

Put the envelopes in whatever order you want. Choose any letter and put it in any envelope **other** than the the one it belongs in. There are n-1 ways to do that. Now choose the letter that belongs in **that** envelope. Choose any of the remaining envelopes to put that one letter in. There are n-1 ways to do that. Proceed in the same manner, at each point, choosing the letter that belongs in the envelope you just filled. That gives a total of (n-1)(n-1)(n-2)...(3)(2)(1)= (n-1)(n-1)! ways to do that.

Re: Inclusion Exclusion Principle?

Quote:

Originally Posted by

**combinatorixxx** Question: n letters belong to n envelopes. How many ways can these be arranged such that each letter is in the wrong envelope?

I'm quite stuck. I was thinking of applying the Inclusion-Exclusion Principle, so taking:

(Total combinations = n!) - |A1 u A2 u ... u An|, where Ai is the set where i letters are in the correct envelope.

Yes that is correct and you end up with the formula for the number of **derangements**,

Now the good news. We do not have to always use that summation.

This works:

It is very accurate and usual for probability.