Definition - Das Prinzip von Inklusion und Exklusion

• Beispiele:
  • Siebformel für Wahrscheinlichkeitsmaße
• Eigenschaften:
  • Siebformel für austauschbare Ereignisse
• Involvierte Definitionen:
  • Ereignis
  • Vereinigung von Ereignissen
• Veranstaltung: AlMa, EiS
• Referenz: } AlgoMathe KE1 - Prinzip von Inklusion und Exklusion, @henze2019

⠀

Definition: Das Prinzip von Inklusion und Exklusion

Das Prinzip von Inklusion und Exklusion ist eine Technik zur Bestimmung der Mächtigkeit von Vereinigungen.

Die allgemeine Formel lautet

Definition: Siebformel der Stochastik

Sei ein Wahrscheinlichkeitsraum.
Seien Ereignisse.

Für sei die Summe der Wahrscheinlichkeit aller -elementigen Durchschnitte, also:

Dann gilt:

Betrachtung und Erläuterung

Man könnte meinen, dass die Kardinalität zweier vereinigter Mengen der Summe ihrer Kardinalitäten

↯

entspricht. Dies ist aber nicht der Fall:

WARNING

Wenn wir zwei Mengen haben, dann gilt für die Mächtigkeit der Vereinigung

nur, wenn und disjunkt sind.

Zwei (2) Nicht-Disjunkte Menge

Sobald und jedoch nicht mehr disjunkt sind, zählen wir mit diesem Vorgehen manche Elemente doppelt.

Transclude of Venn-Diagramm-Schnitt-2-Mengen.excalidraw

und zwar genau die Elemente, die in dem Schnitt der beiden Mengen liegen (hier die ).

Die Lösung ist simpel: wir ziehen die doppelt gezählten Elemente einfach wieder ab:

SUCCESS

Drei (3) Nicht-Disjunkte Menge

Drei nicht-disjunkte Mengen machen das ganze noch einmal komplizierter. Wir betrachten das folgende Beispiel:

Transclude of Venn-Diagramm-Schnitt-3-Mengen.excalidraw

ATTENTION

Wenn wir hier nach dem selben Muster agieren:

ziehen wir die Mengen in drei mal ab.

das heißt: wir müssen noch einmal zu der Formel hinzufügen. Erhalten also als Ergebnis:

SUCCESS

Vier (4) Nicht-Disjunkte Menge

Mit vier disjunkten Mengen ist das ganze noch verrückter.

Transclude of Venn-Diagramm-Schnitt-4-Mengen.excalidraw

Leider sind hier so viele Objekte im Spiel, dass wir nur recht abstrahiert darüber nachdenken können. Im Grunde ist dieser Fall gleich wie der mit drei Mengen - lediglich für die Teilmenge sieht es anders aus. Die wollen wir jetzt genauer untersuchen.

Wir betrachten dazu die Formel, die für diesen Fall korrekt ist.

Jede Zeile in dieser Formel betrachten wir jetzt als einzelnen Schritt. Wir beobachten hier nur, wie häufig die Teilmenge hinzugefügt oder entfernt wird. Wir bezeichnen .

1. Wir fügen jedes Element der Mengen 4-mal hinzu. wird also 4-mal hinzugefügt.
2. befindet sich hier in jedem der Schnitte, daher wird es 6-mal abgezogen
3. befindet sich wieder in jedem der Schnitte, es wird also 4-mal hinzugefügt
4. befindet sich auch in dem letzten Schnitt, wird also 1-mal abgezogen

Wir zählen das zusammen: Wie gewollt, wird am Ende genau 1-mal gezählt.

Verallgemeinerung

Insbesondere die letzte Formel können wir auch wie folgt schreiben:

Was passiert in der Formel? Nun:

• Zuerst ist
  • ist gleich
  • Wir summieren über die Mengen aus der Mengenfamilie . In anderen Worten, wir summieren alle -elementigen Mengen
    • Wir schneiden diese -elementigen Mengen mit sich selbst
    • Wir summieren die Kardinalität des Schnittes auf.
• Jetzt ist
  • ist gleich
  • Wir summieren über die Mengen aus der Mengenfamilie . In anderen Worten, wir summieren alle -elementigen Mengen
  • Wir schneiden die Elemente dieser -elementigen Mengen miteinander
  • Wir summieren die Kardinalität der Schnitte auf.
  • Da ja war, kommt davor noch ein Minus.
• und so weiter

Wir inkludieren und exkludieren (daher der Name) also abwechselnd die Kardinalität von Schnitten von Teilmengen.