◀ ▲ ▶Branches / Combinatorics / Theorem: Inclusion-Exclusion Principle (Sylvester's Formula)

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

Theorem: Inclusion-Exclusion Principle (Sylvester's Formula)

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

Table of Contents

Proofs: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Knauer Ulrich: "Diskrete Strukturen - kurz gefasst", Spektrum Akademischer Verlag, 2001