TU Wien:Mathematik 1 UE (diverse)/Theorie WS05/06.12.2005 Inklusions-Exklusions-Prinzip

Inklusions-Exklusions-Prinzip

Das Inklusions-Exklusions-Prinzip wird in vielen kombinatorischen Anzahlbestimmungsaufgaben eingesetzt.

Um sich das Prinzip klarzumachen, betrachte man zunächst disjunkte Mengen A und B. Dann ist $|A\cup B|=|A|+|B|$.

Sind A und B jedoch nicht disjunkt, so zählt man mit dem Ausdruck $|A|+|B|$ diejenigen Elemente doppelt, die sowohl in A als auch in B vorkommen, d.h. $|A\cap B|$ muß wieder subtrahiert werden, daher gilt:

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

.

Vielfachheit, mit der Elemente in $|A|+|B|$ gezählt werden

Betrachtet man drei Mengen A,B und C, soo werden mit $|A|+|B|+|C|$ alle diejenigen Elemente zu oft gezählt, die in mindestens zwei dieser Mengen gleichzeitig liegen. Subtrahiert man jedoch $|A\cap B|+|A\cap C|+|B\cap C|$, so subtrahiert man diejenigen Elemente zu oft, die in allen drei Mengen liegen; man muß also wieder $|A\cap B\cap C|$ addieren und erhält zusammen:

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

.

Vielfachheit, mit der Elemente in $|A|+|B|+|C|$ gezählt werden

Vielfachheit, mit der Elemente in $|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|$ gezählt werden

Vielfachheit, mit der Elemente in $|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ gezählt werden

Zur Illustration der kombinatorischen Bedeutung dieser Formel interpretiere man die Mengen A,B, C als Eigenschaften von Elementen einer Grundmenge M. Menge A bestehe aus Elementen von M? , die die Eigenschaft $P_{A}$€ haben, B aus den Elementen, die Eigenschaft $P_{B}$€ haben und C aus den Elementen, die die Eigenschaft $P_{C}$€ haben.

Die Anzahl der Elemente, die mindestens eine der Eigenschaften $P_{A}$€, $P_{B}$€ oder $P_{C}$€ƒ besitzen, ist also $|A\cup B\cup C|$.

Oft ist es jedoch schwierig, diese Anzahl direkt anzugeben, jedoch leichter anzugeben, wieviele Elemente Eigenschaft $P_{A}$€€ besitzen, d. h. |A|, u. s.w. und wieviele Elemente die Eigenschaften $P_{A}$€€ und $P_{A}$€€ besitzen, d. h. $|A\cap B|$ u.s.w.

Die betrachtete Formel gibt also einen Zusammenhang zwischen der Anzahl der Elemente, die mindestens eine von gewissen vorgegebenen Eigenschaften besitzen, mit den Anzahlen der Elemente, die eine oder mehrere dieser Eigenschaften zugleich besitzen.

Satz (Siebformel)

Es seien $A_{1},...,A_{n}$ Teilmengen einer endlichen Menge M. Dann gilt:

$|\bigcap _{i=1}^{n}{\overline {A_{i}}}|=|M\backslash \bigcup _{i=1}^{n}A_{i}|=\sum _{I\subset \{1,2,..,n\}}(-1)^{|I|}*\bigcap _{i\in I}A_{i}|$

Anwendung der Siebeformel von Schakal

Für alle die sich fragen wie man nun die Formel anwendet, erläutere ich das an einem Beispiel: Gegeben seien die die Mengen $A_{1},A_{2},A_{3}$. Dadurch erhalten wir

${\Biggl |}\bigcup _{i=1}^{3}A_{i}{\Biggr |}=\sum _{\emptyset \neq I\subseteq \{1,2,3\}}(-1)^{|I|-1}\cdot {\Biggl |}\bigcap _{i\in I}A_{i}{\Biggr |}$

und $I$ nimmt alle alle Elemente von $P(\lbrace 1,2,3\rbrace )\smallsetminus \emptyset$ an. Also nimmt $I$ alle Elemente der Menge $\lbrace \lbrace 1\rbrace ,\lbrace 2\rbrace ,\lbrace 3\rbrace ,\lbrace 1,2\rbrace ,\lbrace 1,3\rbrace ,\lbrace 2,3\rbrace ,\lbrace 1,2,3\rbrace \rbrace$ an. In unserem Fall würde das dazu führen:

$|A_{1}\cup A_{2}\cup A_{3}|=(-1)^{1-1}|A_{1}|+(-1)^{1-1}|A_{2}|+(-1)^{1-1}|A_{3}|+(-1)^{2-1}|A_{1}\cap A_{2}|+(-1)^{2-1}|A_{1}\cap A_{3}|+(-1)^{2-1}|A_{2}\cap A_{3}|+(-1)^{3-1}|A_{1}\cap A_{2}\cap A_{3}|$

Somit ist:

$|A_{1}\cup A_{2}\cup A_{3}|=|A_{1}|+|A_{2}|+|A_{3}|-|A_{1}\cap A_{2}|-|A_{1}\cap A_{3}|-|A_{2}\cap A_{3}|+|A_{1}\cap A_{2}\cap A_{3}|$