Prinzip von Inklusion und Exklusion

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

[Bearbeiten] Das Prinzip

Es ist ein bekanntes Ergebnis, dass für je zwei Mengen $A$ und $B$

$|A \cup B| = |A| + |B| - |A \cap B|$

Im Allgemeinen wollen wir die Kardinalität der Vereinigung von $n$ Mengen

$X = A_1 \cup A_2 \cup \ldots \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 \cap A_j$ mehrfach zählen würden, also

$|X| \leq \sum_{1 \leq i \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

$|X| \geq \sum_{1 \leq i \leq n} |A_i| ~- \sum_{1 \leq i<j \leq n} |A_i \cap A_j|~,$

denn Elemente des Schnittes dreier Mengen $A_i \cap A_j \cap A_k$ würden – obwohl nur zweimal zu häufig bei der Inklusion mitgezählt – durch $|A_i \cap A_j|$ , durch | $A_i \cap A_k|$ und durch | $A_j \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

$|X| \leq \sum_{1 \leq i \leq n} |A_i| ~- \sum_{1 \leq i<j \leq n} |A_i \cap A_j| ~+ \sum_{1 \leq i<j<k \leq n} |A_i \cap A_j \cap A_k|~,$

darauf folgt durch Exklusion

$|X| \geq \sum_{1 \leq i \leq n} |A_i| ~- \sum_{1 \leq i<j \leq n} |A_i \cap A_j| ~+ \sum_{1 \leq i<j<k \leq n} |A_i \cap A_j \cap A_k| ~- \sum_{1 \leq i<j<k<l \leq n} |A_i \cap A_j \cap A_k \cap A_l|~,$

und so weiter.

[Bearbeiten] Satz

Es lässt sich folgende, allgemeine Aussage beweisen. Gegeben seien $n$ Teilmengen $A_1,A_2,\ldots,A_n$ und $X = \bigcup_{i=1}^n A_i$ . Bezeichne im folgenden zu einer Indexmenge $I \subseteq \{1,2,\ldots,n\}$ die Menge $A I$ , den Schnitt über alle durch die Indexmenge gegebenen Teilmengen, also $A_I := \bigcap_{i \in I} A_i$ , wobei $A_\emptyset = X$ entspricht. Dann gilt

$|X| = \sum_{\emptyset \not= I \subseteq \{1,\ldots,n\}} \left( -1\right)^{|I|+1}|A_I|~.$

Mit anderen Worten: Betrachtet man alle möglichen Schnitte $A I$ (außer dem leeren Schnitt $A_\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| = \sum_{{I \subseteq \{1,\ldots,n\},}\atop{|I|~ungerade}} |A_I| - \sum_{{\emptyset \not= I \subseteq \{1,\ldots,n\},}\atop{|I|~gerade}} |A_I|$

[Bearbeiten] Anwendung

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

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

$\mathsf{P}\left(\bigcup_{i=1}^nA_i\right) = \sum_{k=1}^n(-1)^{k+1}\!\!\sum_{I\subseteq\{1,\dots,n\},\atop |I|=k}\!\!\!\!\mathsf{P}\left(\bigcap_{i\in I}A_i\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.

[Bearbeiten] Siehe auch

[Bearbeiten] 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.

Von „http://de.wikipedia.org../../../p/r/i/Prinzip_von_Inklusion_und_Exklusion_51ea.html“

Kategorien: Kombinatorik | Mengenlehre