Learn practical skills, build real-world projects, and advance your career


Probability and Statistics



Question: How many numbers between between 1...1001...100 that are divisible by 33 or 44
let AA=all numbers from 1...1001...100 that are divisible by 33 then A=1003=33|A|=\left \lfloor \frac{100}{3} \right \rfloor=33
let BB=all numbers from 1...1001...100 that are divisible by 44 then B=1004=25|B|=\left \lfloor \frac{100}{4} \right \rfloor=25
and ABA\cup B will contains all numbers between 1...1001...100 that are divisible by 33 or 44, so can we apply Sum rule? no, because ABA\cap B\ne\emptyset
AB=A+B|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 ABA\cap B counted once in A|A| and once in B|B| means they got counted twice but they supposed to be counted only once, so the fix is the following.
AB=A+BAB|A \cup B|=|A|+|B|-|A\cap B| (this is the idea, include and exclude in controlled way)
 AB=33+258=50\therefore ~ |A \cup B|= 33+25-8=50 (AB=10012=8\because |A\cap B|=\left \lfloor \frac{100}{12} \right \rfloor =8 )

Similarly if we have three finite sets A,B,CA,B,C then ABC=A+B+CABBCAC+ABC|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 A1,A2,...,AnA_1,A_2,...,A_n be finite sets. Then
A1A2...An=1inAi1i<jnAiAj+1i<j<knAiAjAk....+(1)r+11i1<i2<...<irnAi1Ai2Ai3...Air+(1)n+1A1A2...An|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)