# Inclusion Exclusion Principle?

• May 10th 2012, 05:54 AM
combinatorixxx
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 :)
• May 10th 2012, 06:06 AM
a tutor
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
• May 11th 2012, 10:28 PM
Sarasij
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
• May 12th 2012, 11:02 AM
HallsofIvy
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.
• May 12th 2012, 03:45 PM
Plato
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, $\mathcal{D}(n).$

$\mathcal{D}(n)=n!\cdot\sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}}$

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

This works: $\mathcal{D}(n) \approx \frac{{n!}}{e}$
It is very accurate and usual for probability.