Inklusions-Exklusions-Prinzip
Das Inklusions-Exklusions-Prinzip zählt die Größe einer Vereinigung von Mengen, indem es abwechselnd die Größen ihrer Schnittmengen addiert und subtrahiert.
Definition
Eine Zählidentität, die besagt, dass die Kardinalität einer Vereinigung endlicher Mengen gleich der alternierenden Summe der Kardinalitäten aller ihrer Schnittmengen ist, genommen über jede nichtleere Unterkollektion.
Scope
Dieses Thema präsentiert die Inklusions-Exklusions-Formel und ihre Anwendungen zum Zählen von Objekten, die eine Liste verbotener Eigenschaften vermeiden: Derangements, Surjektionen, Eulersche Phi-Funktion und die Anzahl der zu einer gegebenen Zahl teilerfremden ganzen Zahlen. Es führt den Sieb-Standpunkt und die Verallgemeinerung der Möbius-Funktion über teilweise geordnete Mengen ein, was das Prinzip in einen breiteren algebraischen Kontext stellt.
Core questions
- Wie viele Elemente erfüllen mindestens eine von mehreren überlappenden Bedingungen?
- Wie kann man Objekte zählen, die alle einer Menge verbotener Eigenschaften vermeiden?
- Wie ergeben sich Derangements- und Surjektionszählungen aus dem Prinzip?
- Wie verallgemeinert die Möbius-Funktion auf einem Poset die Inklusion-Exklusion?
Key concepts
- Vereinigung überlappender Mengen
- Siebmethode
- Derangements mittels Inklusion-Exklusion
- Zählen von Surjektionen
- Eulersche Phi-Funktion
- Möbius-Funktion auf Posets
Key theories
- Inklusions-Exklusions-Formel
- Die Kardinalität einer Vereinigung von Mengen A_1 bis A_n ist gleich der Summe der Größen der einzelnen Mengen abzüglich der paarweisen Schnittmengen plus der dreifachen Schnittmengen und so weiter, wobei systematisch für die Überzählung gemeinsamer Elemente korrigiert wird.
- Möbius-Inversion auf Posets
- Stanleys poset-theoretische Verallgemeinerung ersetzt die alternierenden Vorzeichen der Inklusion-Exklusion durch die Möbius-Funktion einer teilweise geordneten Menge und vereinheitlicht das Prinzip mit zahlentheoretischen und verbandstheoretischen Inversionsformeln.
Clinical relevance
Die Sieb-Idee verallgemeinert sich auf die Zahlentheorie (das Sieb des Eratosthenes und analytische Siebe), die Wahrscheinlichkeitstheorie (die Bonferroni-Ungleichungen zur Begrenzung von Vereinigungswahrscheinlichkeiten) und die Zuverlässigkeitsanalyse von Systemen mit überlappenden Fehlermodi.
History
Im Wesentlichen von de Moivre und Sylvester formuliert, wurde das Prinzip 1964 von Rota in eine allgemeine Theorie der Möbius-Funktionen auf teilweise geordneten Mengen eingeordnet, ein Meilenstein der modernen Kombinatorik.
Key figures
- Abraham de Moivre
- Gian-Carlo Rota
Related topics
Seminal works
- stanley2011
Frequently asked questions
- Warum wechseln die Vorzeichen?
- Elemente, die in mehreren Mengen liegen, werden zu oft addiert; das Subtrahieren paarweiser Schnittmengen überkorrigiert, sodass dreifache Schnittmengen wieder hinzugefügt werden, was das alternierende Muster erzeugt, das jedes Element genau einmal zählt.
- Welche Verbindung besteht zur Möbius-Funktion?
- Die Inklusion-Exklusion ist der Spezialfall der Möbius-Inversion auf dem Booleschen Verband der Teilmengen, wobei die Möbius-Funktion die Werte plus oder minus eins annimmt.