Friday 6 March 2015

Inclusion–exclusion principle



When we number the regions of different sets, we can easily see that

$\underbrace{n(A\cup B \cup C)}_{1234567}\\
=\underbrace{n(A)}_{1347}+\underbrace{n(B)}_{1246}+\underbrace{n(C)}_{1235}-\underbrace{n(A\cap B)}_{14}-\underbrace{n(A\cap C)}_{13}-\underbrace{n(B\cap C)}_{12}+\underbrace{(A\cap B\cap C)}_{1}$

The elements in each of regions 1 through 7 are counted once on both the LHS and RHS.