INEX

INEX

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 Mächtigkeit 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 von oben abgeschätzt wird (Inklusion), anschließend jedoch durch die Subtraktion der Größe des gemeinsamen Schnittes der Teilmengen dies wieder zu korrigieren versucht wird (Exklusion).

Inhaltsverzeichnis

Das Prinzip

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

|A \cup B| = |A| + |B| - |A \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 \cup B| von oben abgeschätzt. Dieser Fehlbetrag wird anschließend durch |A \cap B| korrigiert. Zweck dieser Korrektur ist es, diejenigen Elemente wieder abzuziehen, die sowohl in A, als auch in B enthalten sind und somit zunächst doppelt gezählt wurden.

Im Allgemeinen wollen wir die Kardinalität der Vereinigung von n endlichen 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 Ai. 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.

Satz

Es lässt sich folgende, allgemeine Aussage beweisen. Gegeben sei eine endliche Menge X, die sich als eine Vereinigung von n Teilmengen A_1,A_2,\ldots,A_n schreiben lässt, d.h. X = \bigcup_{i=1}^n A_i. Bezeichne im Folgenden zu einer Indexmenge I \subseteq \{1,2,\ldots,n\} die Menge AI , 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 AI (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|

Anwendung

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

Für die Wahrscheinlichkeit von beliebigen Ereignissen Ai 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.

Siehe auch

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.

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • INEX — may mean: *Internet Neutral Exchange, Ireland. *The Legends car racing rules body …   Wikipedia

  • Inex — steht für: einen Zyklus in der Abfolge von Sonnen und Mondfinsternissen, siehe Inexzyklus kurz für die Band In Extremo Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezeichneter Begriffe …   Deutsch Wikipedia

  • Inex — Para Escala Internacional de Accidentes Nucleares, véase INES. El Periodo Inex es un ciclo de eclipses de aproximadamente 29 años. El ciclo lo describió primero Crommelin en 1901, pero recibió su nombre de G. van den Bergh que lo estudió medio… …   Wikipedia Español

  • Inex — The inex is an eclipse cycle of about 29 years. The cycle was first described by Crommelin in 1901, but was named by George van den Bergh who studied it half a century later.An inex is 358 lunations (synodic months) long: this is almost exactly… …   Wikipedia

  • Inex — Pour les articles homonymes, voir Inex (homonymie). L inex est une durée égale à 358 lunaisons (ou mois synodiques), soit environ 28 ans et 50 semaines. L inex a la propriété intéressante d être également proche d un nombre demi entier de fois la …   Wikipédia en Français

  • Inex-Adria Aviopromet Flight 1308 — CG render of YU ANA Accident summary Date December 1, 1981 …   Wikipedia

  • Inex-Zyklus — Ein Inexzyklus ist eine Reihe (Zyklus) von Sonnen oder Mondfinsternissen. Seine Periode, die Inexperiode, ist etwa 29 Jahre weniger 20 Tage lang. Der Inexzyklus ist ein Finsterniszyklus, der als einzelne Reihe theoretisch etwa 809 Finsternisse… …   Deutsch Wikipedia

  • Inex (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Le terme inex peut désigner plusieurs choses : l inex est une durée en rapport avec l astronomie l Inexplosible est un bateau sur la Loire, à Orléans …   Wikipédia en Français

  • Inex (bâteau) — Inexplosible L Inexplosible no 22 L Inexplosible, de son nom complet « Inexplosible n°22 », est un bateau à roues amarré sur la Loire à Orléans, est une reproduction d un ancien navire du même nom …   Wikipédia en Français

  • Hotel Inex Gorica — (Охрид,Македония) Категория отеля: Адрес: 7 Naum Ohridski str., 6000 Охрид, Македон …   Каталог отелей

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”