inclusion-exclusion principle

The inclusion -exclusion principle gives a way to compute the size of the union of multiple non-disjoint sets.

$|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|$

→

Inclusion-Exclusion Principle

$n\ge 1$

$$\begin{array}{rl}|\bigcup _{i=1}^n{A}_i|& =\sum _{i=1}^n|A_i|-\sum _{i<j}|A_i\cap A_j|+\sum _{i<j<k}|A_i\cap A_j\cap A_k|-\cdots +(-1{)}^{n-1}|A_1\cap \cdots \cap A_n|\\ & =\sum _{i=1}^n(-1{)}^{i-1}|\bigcap _{j=1}^i{A}_j|\end{array}$$

EXAMPLE

alphabet $\Sigma =\{a,b,c,d,e\}$, set of words (order matters), ${\Sigma }^{\ast }=\{x_1{x}_2\dots x_n|x_i\in \Sigma \}$, empty word $ϵ$.
$W=\{w\in {\Sigma }^{\ast }:w\text{ contains }a,b,c\}$, length $n$
$|W|=?$ … how big is the set of words containing $a,b,c$?
$W={\Sigma }^{\ast }\setminus (W_a\cup W_b\cup W_c)$ … words that don’t contain $a,b,c$
…???