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

ist

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

Bei drei Mengen

ist


Es sei eine Menge und es seien , , endliche Teilmengen. Für eine Teilmenge sei

Dann ist

Wir beweisen die Aussage durch Induktion über , wobei der Fall klar ist. Für siehe Aufgabe. Es ist

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

je nachdem aufspaltet, ob dazu gehört oder nicht.


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 . Dann gibt es für die Teilmengen nur die Möglichkeiten oder . Wir können annehmen, dass

und

ist. Zu einer Teilmenge ist dann einelementig genau dann, wenn ist, und sonst immer leer. Daher ist die rechte Seite gleich

Dies ist bei gleich und sonst nach Aufgabe gleich , was mit der linken Seite übereinstimmt.


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 gegeben, mit denen man den Sand sieben möchte. Dann ist die Menge der Sandkörner, die durch das Sieb durchfallen, und zu einer Teilmenge ist dann die Menge der Sandkörner, die durch die Siebe , , (wenn man sie übereinander hält) durchfallen.