Siebformel/Einführung/Textabschnitt

Die Siebformel berechnet die Anzahl in einer Vereinigung von Mengen, wenn die einzelnen Anzahlen der Mengen und ihrer Durchschnitte bekannt sind. Im einfachsten Fall, bei

${}M=A\cup B\,,$

ist

${}{\#\left(M\right)}={\#\left(A\right)}+{\#\left(B\right)}-{\#\left(A\cap B\right)}\,.$

Um die Elemente, die sowohl in ${}A$ als auch in ${}B$ sind, nicht doppelt zu zählen, muss man deren Anzahl abziehen.

Bei drei Mengen

${}M=A\cup B\cup C\,,$

ist

${}{\#\left(M\right)}={\#\left(A\right)}+{\#\left(B\right)}+{\#\left(C\right)}-{\#\left(A\cap B\right)}-{\#\left(A\cap C\right)}-{\#\left(B\cap C\right)}+{\#\left(A\cap B\cap C\right)}\,.$

Satz

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

Wir beweisen die Aussage durch Induktion über ${}n$, wobei der Fall ${}n=1$ klar ist. Für ${}n=2$ siehe Aufgabe. Es ist

${}{\begin{aligned}{\#\left(\bigcup _{i=1}^{n+1}A_{i}\right)}&={\#\left({\left(\bigcup _{i=1}^{n}A_{i}\right)}\cup A_{n+1}\right)}\\&={\#\left(\bigcup _{i=1}^{n}A_{i}\right)}+{\#\left(A_{n+1}\right)}-{\#\left({\left(\bigcup _{i=1}^{n}A_{i}\right)}\cap A_{n+1}\right)}\\&=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}+{\#\left(A_{n+1}\right)}-{\#\left(\bigcup _{i=1}^{n}{\left(A_{i}\cap A_{n+1}\right)}\right)}\\&=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}+{\#\left(A_{n+1}\right)}-\sum _{\ell =1}^{n}(-1)^{\ell +1}{\left(\sum _{L\subseteq \{1,\ldots ,n\},\,{\#\left(L\right)}=\ell }{\#\left(A_{L}\cap A_{n+1}\right)}\right)}\\&=\sum _{k=1}^{n+1}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,n+1\notin J,\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}+\sum _{k=1}^{n+1}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,{\#\left(J\right)}=k,\,n+1\in J}{\#\left(A_{J}\right)}\right)}\\&=\sum _{k=1}^{n+1}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)},\end{aligned}}$

wobei wir für die zweite Gleichung den Fall von zwei Teilmengen und für die dritte und die vierte Gleichung die Induktionsvoraussetzung verwendet haben. Für die fünfte Gleichung führen wir hinten die Indexverschiebung ${}k=\ell +1$ durch und der mittlere Term wird in die rechte Summe integriert. Die sechste Gleichung ergibt sich von unten nach oben gelesen, wenn man die Teilmengen

${}J\subseteq \{1,\ldots ,n,n+1\}\,$

je nachdem aufspaltet, ob ${}n+1$ dazu gehört oder nicht.

$\Box$

Man spricht auch vom Prinzip der Inklusion und Exklusion. Wir geben noch einen zweiten Beweis für die vorstehende Aussage.

Beide Seiten der Siebformel verhalten sich additiv, wenn eine disjunkte Zerlegung der Grundmenge vorliegt. Deshalb genügt es, die Aussage für eine einelementige Menge zu zeigen (man fragt sich für jedes Element, wie oft es links und wie oft es rechts gezählt wird). Sei also ${}G=\{x\}$. Dann gibt es für die Teilmengen ${}A_{i}$ nur die Möglichkeiten ${}A_{i}=\{x\}$ oder ${}A_{i}=\emptyset$. Wir können annehmen, dass

${}A_{1}=\ldots =A_{r}=\{x\}\,$

und

${}A_{r+1}=\ldots =A_{n}=\emptyset \,$

ist. Zu einer Teilmenge ${}J\subseteq {\{1,\ldots ,n\}}$ ist dann ${}A_{J}=\{x\}$ einelementig genau dann, wenn ${}J\subseteq {\{1,\ldots ,r\}}$ ist, und sonst immer leer. Daher ist die rechte Seite gleich

${}{\begin{aligned}\sum _{k=1}^{r}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,r\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}&=\sum _{k=1}^{r}(-1)^{k+1}\sum _{J\subseteq \{1,\ldots ,r\},\,{\#\left(J\right)}=k}1\\&=\sum _{k=1}^{r}(-1)^{k+1}{\binom {r}{k}}.\end{aligned}}$

Dies ist bei ${}r=0$ gleich ${}0$ und sonst nach Aufgabe gleich ${}1$, was mit der linken Seite übereinstimmt.

Bemerkung  

Die Bezeichnung „Siebformel“ kann man sich folgendermaßen erklären: Es sei eine Menge von Sandkörnern, Kristallen oder Diamanten gegeben, die unterschiedliche Größen und Formen besitzen. Es sei eine Menge von Sieben ${}S_{1},\ldots ,S_{n}$ gegeben, mit denen man den Sand sieben möchte. Dann ist ${}A_{i}$ die Menge der Sandkörner, die durch das Sieb ${}S_{i}$ durchfallen, und zu einer Teilmenge ${}J\subseteq {\{1,\ldots ,n\}}$ ist dann ${}A_{J}$ die Menge der Sandkörner, die durch die Siebe ${}S_{i}$, ${}i\in J$, (wenn man sie übereinander hält) durchfallen.