General formula for union of n sets
Emily Wong 
So for two and three sets I have:$$|A\cup B| = |A| +|B| - |A \cap B|,$$
$$|A\cup B\cup C| = |A| + |B| +|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|.$$
What is the general solution for $n$ sets? Thank you!
For example if I want to find the area for n overlapping rectangles (at different angles or radii etc). what is the general formula? I want to know what combinations I need to add and subtract to achieve this.
3 Answers
$\begingroup$The general formula is known as Poincaré's formula or inclusion-exclusion formula. It is an alternating sum which goes like this (the sum is finite since $r\le n$):$$\biggl|\bigcup_{i=1}^n A_i\biggr|=\sum_{i=1}^n\bigl|A_i\bigr|-\sum_{1\le i<j\le n}^n\bigl|A_i\cap A_j\bigr|+\dots+(-1)^r\mkern -1.5em\sum_{\substack{1\le i_1<\dots<i_r\le n}}^n\mkern -1.5em\bigl|A_{i_1}\cap\dots\cap A_{i_r}\bigr|+\dotsm$$
$\endgroup$ $\begingroup$Calling $[n]=\{m\in \mathbb{N}\mid 1\le m\le n\}$ where $n\in \mathbb{N}$ then $$|\bigcup_{i\in [n]}A_i |=\sum_{J\subseteq [n]}(-1)^{|J |+1 }|\bigcap_{j\in J}A_j|$$
$\endgroup$ $\begingroup$Note: This uses nonstandard, but natural, notation for indicator functions. I show this more to show how the formula may be derived from a simple observation.
If we start with a given universe $U,$ which is just a set such that every $A_i$ is a subset of it, then this is just a consequence of$$\left(\bigcup_{i=1}^n A_i\right)^c = \bigcap_{i=1}^n A_i^c$$or in words, an element is not in the union of all the sets exactly when it is in none of the sets.
At the level of indicator functions, this is$$1 - \bigcup_{i=1}^n A_i = \left(\bigcup_{i=1}^n A_i\right)^c = \bigcap_{i=1}^n A_i^c = \prod_{i=1}^n (1-A_i) \\ \implies \\ \bigcup_{i=1}^n A_i = 1 - \prod_{i=1}^n (1-A_i)$$which expands to give you precisely the inclusion-exclusion formula quoted by others, but in terms of indicators.
$\endgroup$
