Thread: 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

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

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

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.

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.