103 lines
4.8 KiB
XML
103 lines
4.8 KiB
XML
#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$) |