MA2102

Probability and Statistics

Lecture-3

Inclusion-Exclusion

Question: How many numbers between between $1...100$ that are divisible by $3$ or $4$
let $A$=all numbers from $1...100$ that are divisible by $3$ then $|A|=\left \lfloor \frac{100}{3} \right \rfloor=33$
let $B$=all numbers from $1...100$ that are divisible by $4$ then $|B|=\left \lfloor \frac{100}{4} \right \rfloor=25$
and $A\cup B$ will contains all numbers between $1...100$ that are divisible by $3$ or $4$, so can we apply Sum rule? no, because $A\cap B\ne\emptyset$
$|A\cup B|=|A|+|B|$ would be wrong, and count more because some numbers got over counted, but we can fix it. Because we can see what exactly getting over counted, numbers in $A\cap B$ counted once in $|A|$ and once in $|B|$ means they got counted twice but they supposed to be counted only once, so the fix is the following.
$|A \cup B|=|A|+|B|-|A\cap B|$ (this is the idea, include and exclude in controlled way)
$\therefore ~ |A \cup B|= 33+25-8=50$ ($\because |A\cap B|=\left \lfloor \frac{100}{12} \right \rfloor =8$ )

Similarly if we have three finite sets $A,B,C$ then $|A \cup B \cup C|=|A|+|B|+|C|-|A\cap B|-|B \cap C|-|A\cap C|+|A\cap B\cap C|$

Thoerem(Principle of Inclusion and Exclusion): Let $A_1,A_2,...,A_n$ be finite sets. Then
$|A_1\cup A_2\cup ...\cup A_n|=\sum_{1\le i\le n}|A_i|-\sum_{1\le i<j\le n}|A_i\cap A_j|+\sum_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-....+(-1)^{r+1}\sum_{1\le i_1<i_2<...<i_r\le n}|A_{i_1}\cap A_{i_2}\cap A_{i_3}...\cap A_{i_r}|+(-1)^{n+1}|A_1\cap A_2\cap ...\cap A_n|$
proof: by induction on n(you try using base case for n=2)