Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Additionssatz aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Prinzip von Inklusion und Exklusion

Das Prinzip von Inklusion und Exklusion (auch Prinzip der Einschließung und Ausschließung oder Einschluss/Ausschluss-Verfahren) ist eine hilfreiche Technik zur Bestimmung der Kardinalität einer Menge. Sie findet vor allem in der Kombinatorik und in der Zahlentheorie Anwendung.

Das Prinzip drückt dazu die Kardinalität einer Ursprungsmenge $X$ durch die Kardinalitäten ihrer Teilmengen aus. Diese sind in aller Regel einfacher zu bestimmen. Namensgebend ist dabei das Vorgehen, bei welchem zunächst durch die Summe der Größe nicht notwendigerweise disjunkter Teilmengen die Größe von $X$ überschätzt wird (Inklusion), anschließend jedoch durch die Subtraktion der Größe des gemeinsamen Schnittes der Teilmengen dies wieder zu korrigieren versucht wird (Exklusion).

Das Prinzip

Es ist ein bekanntes Ergebnis, dass für je zwei Mengen $A$ und $B$
:$|A\; \backslash cup\; B|\; =\; |A|\; +\; |B|\; -\; |A\; \backslash cap\; B|$
gilt. Hierbei kann man bereits das Prinzip von Inklusion und Exklusion erkennen. Durch $|A|\; +\; |B|$ wird zunächst die Kardinalität von $|A\; \backslash cup\; B|$ überschätzt. Dieser Fehlbetrag wird anschließend durch $|A\; \backslash cap\; B|$ korrigiert.

Im Allgemeinen wollen wir die Kardinalität der Vereinigung von $n$ Mengen
:$X\; =\; A\_1\; \backslash cup\; A\_2\; \backslash cup\; \backslash ldots\; \backslash cup\; A\_n$
bestimmen. Als erste Näherung erhalten wir durch Inklusion die Summe der Kardinalitäten der $A\_i$. Diese Summe ist in aller Regel jedoch zu groß, da wir Elemente aus dem Schnitt zweier Mengen $A\_i\; \backslash cap\; A\_j$ mehrfach zählen würden, also
:$/\text{'}>X|\; \backslash leq\; \backslash sum\_\{1\; \backslash leq\; i\; \backslash leq\; n\}\; |A\_i|~.$
Um dies zu korrigieren können wir nun durch Exklusion die Summe über die Kardinalität aller paarweisen Schnittmengen wieder abziehen. Dann gilt jedoch
:
denn Elemente des Schnittes dreier Mengen $A\_i\; \backslash cap\; A\_j\; \backslash cap\; A\_k$ würden ? obwohl nur zweimal zu häufig bei der Inklusion mitgezählt ? durch $|A\_i\; \backslash cap\; A\_j|$, durch |$A\_i\; \backslash cap\; A\_k|$ und durch |$A\_j\; \backslash cap\; A\_k|$ dreimal wieder abgezogen. Dies nun durch Inklusion, also durch Addition der Summe der Größe aller Schnitte aus drei Mengen, zu korrigieren führt zu
:
darauf folgt durch Exklusion
:
und so weiter.

Satz

Es lässt sich folgende, allgemeine Aussage beweisen. Gegeben seien $n$ Teilmengen $A\_1,A\_2,\backslash ldots,A\_n$ und $X\; =\; \backslash bigcup\_\{i=1\}^n\; A\_i$. Bezeichne im folgenden zu einer Indexmenge $I\; \backslash subseteq\; \backslash \{1,2,\backslash ldots,n\backslash \}$ die Menge $A\_I$ , den Schnitt über alle durch die Indexmenge gegebenen Teilmengen, also $A\_I\; :=\; \backslash bigcap\_\{i\; \backslash in\; I\}\; A\_i$, wobei $A\_\backslash emptyset\; =\; X$ entspricht. Dann gilt
:$|X|\; =\; \backslash sum\_\{\backslash emptyset\; \backslash not=\; I\; \backslash subseteq\; \backslash \{1,\backslash ldots,n\backslash \}\}\; \backslash left(\; -1\backslash right)^\{|I|+1\}|A\_I|~.$
Mit anderen Worten: Betrachtet man alle möglichen Schnitte $A\_I$ (außer dem leeren Schnitt $A\_\backslash emptyset$), so entspricht die Kardinalität von $X$ der Summe der Kardinalität aller Schnitte einer ungeraden Anzahl an Teilmengen (Inklusion) weniger der Summe der Kardinalität aller Schnitte einer geraden Anzahl an Teilmengen (Exklusion), formal:
:$|X|\; =\; \backslash sum\_\; |A\_I|\; -\; \backslash sum\_\; |A\_I|$

Anwendung

Eine Anwendung des Prinzips liefert die Siebformel von Sylvester oder Additionssatz für Wahrscheinlichkeiten:

Für die Wahrscheinlichkeit von beliebigen Ereignissen $A\_i$ gilt:

:$\backslash mathsf\{P\}\backslash left(\backslash bigcup\_\{i=1\}^nA\_i\backslash right)\; =\; \backslash sum\_\{k=1\}^n(-1)^\{k+1\}\backslash !\backslash !\backslash sum\_\{I\backslash subseteq\backslash \{1,\backslash dots,n\backslash \},\backslash atop\; |I|=k\}\backslash !\backslash !\backslash !\backslash !\backslash mathsf\{P\}\backslash left(\backslash bigcap\_\{i\backslash in\; I\}A\_i\backslash right)$.

Aufgrund der Eigenschaft von Maßen, additiv zu sein, lässt sich der oben angegebene heuristische Beweis für das Prinzip von Inklusion und Exklusion, der mit Mitteln der elementaren Mengentheorie geführt wurde, direkt auf Wahrscheinlichkeiten übertragen.

Siehe auch

Bonferroni-Ungleichung
doppeltes Abzählen
Schubfachprinzip

Literatur

Klaus Dohmen, Improved Bonferroni Inequalities via Abstract Tubes - Inequalities and Identities of Inclusion-Exclusion Type, Springer-Verlag, 2003, ISBN 3-540-20025-8.
Stasys Jukna, Extremal Combinatorics, Springer, Mai 2001, ISBN 3-540-66313-4.

       VIDEO-NEWS UND ANGEBOTE