Direkt zum Inhalt

Lexikon der Mathematik: Inklusions-Exklusionsprinzip

Berechnungsmethode zur Lösung folgendes Problems:

Sei S eine endliche Menge und E1, …, Em Eigenschaften der Elemente von S. Wieviele Elemente aus S besitzen keine der angegebenen Eigenschaften?

Anders ausgedrückt: Sei Ai ≔ {aS : a erfüllt Ei}, i = 1,…, m. Wieviele Elemente hat die Menge \begin{eqnarray}S\backslash \displaystyle \underset{i=1}{\overset{m}{\cup }}{A}_{i}?\end{eqnarray}

Das Problem wird auf folgende Weise gelöst: Wir nehmen alle Elemente von S, subtrahieren von |S| die Zahl jener Elemente, die mindestens eine Eigenschaft besitzen, addieren die Zahl jener, die mindestens zwei Eigenschaften besitzen usw. – daher der Name. Es ergibt sich so die folgende Lösung: \begin{eqnarray}\begin{array}{ll}|S-{\cup }_{i=1}^{m}| & =|S|\\ & -\displaystyle {\sum }_{i=1}^{m}|{A}_{i}|\\ & +\displaystyle {\sum }_{i\lt j}|{A}_{i}\cap {A}_{j}|\\ & \pm \ldots \\ & +{(-1)}^{m}|{A}_{i}\cap \cdots \cap {A}_{m}|.\end{array}\end{eqnarray}

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.