Endliche Menge/Siebformel/Fakt

Siebformel

Es sei ${}G$ eine Menge und es seien ${}A_{i}\subseteq G$ , ${}i=1,\ldots ,n$ , endliche Teilmengen. Für eine Teilmenge ${}J\subseteq {\{1,\ldots ,n\}}$ sei

{}A_{J}=\bigcap _{i\in J}A_{i}\,.

Dann ist

${}{\#\left(\bigcup _{i=1}^{n}A_{i}\right)}=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}\,.$

Beweis 1, 2, Alternativen Beweis erstellen

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.