BranchesHistoryHelpLogin
Welcome guest
You're not logged in.
264 users online, thereof 1 logged in

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

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

1.Proof: (related to "Inclusion-Exclusion Principle (Sylvester's Formula)")

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 4.0 by:

This work is a derivative of:

Bibliography (further reading)

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