The coat problem:
A large number of people enter a room and check their coat at the door. Later, upon exiting, everyone is given a coat at random.
Question: What is the probability that everyone gets the wrong coat?

Of course the probability that everyone gets the right coat is just 1/n!, since there are n! ways of arranging the n coats and only 1 of those ways is where everyone gets the right coat. This problem is one of my favorites. The solution involves the principle of inclusion and exclusion of set theory. The problem is equivalent to asking how many permutations are there of n objects where none are in their natural order. This is called the derangements of n, and it is symbolized by !n

Notation for coat problem:
A = person "A" gets the wrong coat
B = person "B" gets the wrong coat
etc...
|A| = number of ways person "A" gets the wrong coat
|B| = number of ways person "B" gets the wrong coat
etc...
|A∪B| = number of ways person "A" or person "B" gets the wrong coat
|A∩B| = number of ways person "A" and person "B" gets the wrong coat
etc...
P(X) = probability of X

Case of 2 people:
AB
BA

|A∪B|=|A|+|B|−|A∩B|
|A∩B|=|A|+|B|−|A∪B|
|A∩B|=1+1−(2!−1)
|A∩B|=1
∴ P(A∩B)=1/2=0.5

Case of 3 people:
ABC
ACB
BAC
BCA
CAB
CBA

|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|
|A∩B∩C|=−|A|−|B|−|C|+|A∩B|+|A∩C|+|B∩C|+|A∪B∪C|
|A∩B∩C|=−4−4−4+3+3+3+(3!−1)
|A∩B∩C|=2
∴ P(A∩B∩C)=2/6=0.3333...

Case of 4 people:

|A∪B∪C∪D|=|A|+|B|+|C|+|D|−|A∩B|−|A∩C|−|A∩D|−|B∩C|−|B∩D|−|C∩D|+|A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D|−|A∩B∩C∩D|
|A∩B∩C∩D|=|A|+|B|+|C|+|D|−|A∩B|−|A∩C|−|A∩D|−|B∩C|−|B∩D|−|C∩D|+|A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D|−|A∪B∪C∪D|
|A∩B∩C∩D|=18+18+18+18−14−14−14−14−14−14+11+11+11+11−(4!−1)
|A∩B∩C∩D|=9
∴ P(A∩B∩C∩D)=9/24=0.375

Case of n people:
|A₁∪ A₂∪ A₃...∪ A_n|= ∑|A_i|−∑|A_i ∩ A_j|+∑|A_i ∩ A_j ∩ A_k| − + ...+(−1)ⁿ |A_i ∩ A_j ∩ A_k ... ∩ A_n|

where 1≦ i<j<k...<n

!n = ∑[(−1)^k+1(n!(n!−(n−k)!/(k!(n−k)!)] where k=1,2,...n

!2=1
!3=2
!4=9
!5=44
!6=265
...

As n→∞, P(A₁∩A₂∩A₃...∩A_n) = !n/n! = 1/e