#title[Inclusion/Exclusion]
Section 8.5+8.6

The hat problem: Suppose everyone one in a classroom has a hat, and they put their hat in a box when they enter, and then grab a random hat when they leave. What is the probability that everybody gets their own hat. Answer is $1/n!$

What about the probability that _someone_ will not get their own hat: $1-1/n!$

What about the probability that someone will get their own hat, or that no one? Need inclusion/exclusion. The probability that no one will get their own hat is $37.8%$ pretty much no matter how many people.

*Remember:*

$|A union B| = |A| + |B| - |A inter B|$ 

and 

$|A union B union C| = |A|+|B|+|C| - |A inter B| - |A inter C| - |B inter C| + |A inter B inter C|$

== Formula
$ |A_1 union A_2 union dots union A_n| = |A_1| + |A_2| + dots + |A_n| - |A_1 inter A_2| - |A_1 inter A_3| - ... - |A_(n-1) inter A_n|\ 
+ |A_1 inter A_2 inter A_3| + |A_1 inter A_2 inter A_4| + dots + |A_(n-2) inter A_(n-1) inter A_n)|\
- |A_1 inter A_2 inter A_3 inter A_4| - dots - |A_(n-3) inter A_(n-2) inter A_(n-1) inter A_(n)|\
+ |A_1 inter A_2 inter A_3inter A_4 inter A_5| + dots + |A_(n-4) inter A_(n-3) inter A_(n-2) inter A_(n-1) inter A_(n)|\ 
dots dots (-1)^(n+1) |A_1 inter A_2 inter dots inter A_n| $

$ =sum_(i=1)^n |A_i|- sum_(i<=i_1<i_2<=n) |A_i_1 inter A_i_2| + dots + (-1)^(k+1) sum_(i_1<i_2<dots<i_k)|A_i_1 inter A_i_2 inter dots inter A_i_k| + dots + (-1)^(n+1)|A_1 inter dots inter A_n| $

Proof: Focus on any $x in A_1 union A_2 union dots union A_n$ and see how many times it is counted. Let $k$ be the number of $i$ such that $x in A_i$

$ -mat(k;0) + mat(k;1)-mat(k;2)+mat(k;3)-mat(k;4)+mat(k;5)-dots + (-1)^(k+1) mat(k;k) + 1 = 1 $
(The reason we write $+1$ is because $-mat(k;0)=-1$)

Ignoring the $+1$, the rest is a row in Pascals triangle, and we now the alternating sum (+, then -, then +) is 0, so we know the whole thing will be 1.

Consider a set `A` with `N` elements. Properties $P_1, P_2, P_3, dots, P_n$ which means that some elements have the property and some doesn't. $N(P_3 P_5 P_6 P_9) = $ number of elements with each of the properties $P_3 P_5 P_6 P_9$

$N(P_(3) ' P_(5) ' P_6 ' P_9 ') = $ the number of elements with none of the properties $P_3 P_5 P_6 P_9$

*Inclusion/Exclusion:*
$ N(P_1 'P_2 'dots P_n ') = N - sum^n_(i=1)N(P_i) + sum_(i_1 < i_2)N(P_i_1 P_i_2) dots + (-1)^n N(P_1 P_2 dots P_n) $

*Proof:* Put $A_i=$ the elements with property $P_i$ 


`m` balls in `n` boxes. We want to count the number of ways to put `m` balls into `n` boxes such that no box is empty. It follows $m>=n$.

$A = $ all functions of $S->B={1,2,3,dots,n}$
$A_i = $ all functions such that `i` is not in the image.

$ |A\\ union_(i=1)^n A_i| = |A|-|union_(i=1)^n A_i| = n^m-mat(n;1)(n-1)^m +mat(n;2)(n-2)^m-dots (-1)^n mat(n;n)(n-n)^m $

= Permutations of an n-set {1,2,3,4}
Normally a permutation of a set is the elements put on a row (like here $2,3,1,4$ and  $3,1,4,2$).

You can think of permutations as a bijection (different elements should be mapped to different elements, and every element needs to be mapped to an element) from ${1,2,3,4}$ to ${1,2,3,4}$:
$ mat(1,2,3,4;2,3,1,4) $
Notice the 4, mapped unto itself, it's called a fixed point. The 4's would also be a fixed point here:
$ mat(1,2,4,3;2,3,4,1) $
But then its a different set at the top.

== Derangement
A bijection ($pi$) of a set `S` unto itself with no fixed points.

That is $pi(i) eq.not i$

The hat problem: to find the chances of noone getting their own hat, just  use derangements.

== Counting permutations
$A$ is the set of all permutations of ${1,2,dots,n}$

$A_i =$ the set of permutations $pi$ such that $pi(i)=i$

$ 
D_n &=|A\\(union_(i=1)^n) = |A| - sum_(i=1)^n + sum_(i_1<i_2)|A_i_i inter A_i_2| - dots (-1)^n|A_1 inter A_2 inter dots inter A_n|\ 
= n! - mat(n;1)(n-1)! + mat(n;2)(n-2)! - &mat(n;3)(n-3)!+dots (-1)^k mat(n;k)(n-k)! plus.minus dots |A_1 inter A_2 inter dots inter A_n|\
&= sum_(k=0)^n (-1)^k mat(n;k)(n-k)!\
&= sum_(k=0)^n (-1)^k n!/(k!(n-k)!) (n-k)!\
&=n! sum_(k=0)^n (-1)^k/k!\
&= k! [1- 1/1! + 1/2! - 1/3! + dots (-1)^n 1/(n!)]
$
$D_n$ is the permutations

$ 
1&=1/2+1/4+1/8+1/16+1/32+dots\
1&=0.99999999dots\
exp(x)&=1+x/1!+x^2/2!+x^3/3!+dots\
exp(1)&=e=1+1/2!+1/3!+dots\
exp(-1)&=e^-1=1/e=1-1/2!+1/3!-1/4!+dots
$
$exp(-1)$ is what we had before, so
$ D_n &= k! [1- 1/1! + 1/2! - 1/3! + dots (-1)^n 1/(n!)]=n! dot 1/e\
&= n! 1/(2.7dots)= 0.378 n!
$

= Counting primes
The number of primes $<= 100$. The same as saying $100-"not primes"$

Put $ A&={1,2,dots,100}\ A_2 &="The numbers divisible by 2"\ A_3&="The numbers divisible by 3"\ A_5&="The numbers divisible by 5"\ A_7&="The numbers divisible by 7" $

Number of primes 
$ &=100-|A_2 union A_3 union A_5 union A_7|-1+4 - |A_2|-|A_3|-|A_5|-|A_7|+|A_2 inter A_3|+dots\
&=103-50-33-20-14+16+14+6+dots=25
$
($-1$ because 1 is not a prime, and $+4$ because else we're excluding $2,3,5,7$)