The following formula is due to James Sylvester (1814 – 1897).

Let $B_1,\ldots,B_\rho$ be sets. The cardinality of their union $$B:=\bigcup_{r=1}^\rho B_r$$ can be calculated using the so-called **inclusion-exclusion principle**:

$$\begin{align}|\mathbf{B}|&=\sum_{r=1}^\rho|B_r|\nonumber\\

&-\sum_{1\le r<s\le\rho}|(B_r\cap B_s)|\nonumber\\

&+\sum_{1\le r<s<t\le\rho}|(B_r\cap B_s\cap B_t)|\nonumber\\

&\vdots\nonumber\\

&+(-1)^{\rho-1}|(B_1\cap\ldots\cap B_\rho)|\nonumber\end{align}$$

| | | | | created: 2020-05-17 12:34:50 | modified: 2020-05-17 12:48:03 | by: *bookofproofs* | references: [577]

[577] **Knauer Ulrich**: “Diskrete Strukturen – kurz gefasst”, Spektrum Akademischer Verlag, 2001