∪

Inklusion-Exklusion-Rechner

Set Union · PIE Formula · Venn-Diagramm · Wahrscheinlichkeit

Berechne |A∪B∪C∪D| für 2, 3 oder 4 Mengen mit dem Prinzip von Inklusion und Exklusion. Schritt-für-Schritt-Lösung und optionale Wahrscheinlichkeitsberechnung.

Schnellbeispiele

Einzelne Mengen

|A|

|B|

Schnittmengen

|A∩B|

Optional

|U| (Universelle Menge)

|A∪B|

—

Größe der Vereinigung

Addierte Terme

—

Positive Terme

Subtrahierte Terme

—

Negative Terme

Schritt-für-Schritt-Lösung

Venn-Diagramm

Bereichsaufteilung (15 nicht-leere Teilmengen)

Jede Zeile zeigt einen Schnittmengenterm, sein Vorzeichen, seinen Wert und die laufende Summe.

Term	Vorzeichen	Wert	Laufende Summe

Was ist das Prinzip der Inklusion-Exklusion?

Das Prinzip von Inklusion und Exklusion (PIE) ist eine grundlegende Zähltechnik in der Kombinatorik und Mengenlehre. Es liefert eine exakte Formel für die Größe der Vereinigung überlappender endlicher Mengen, indem es abwechselnd die Größen von Schnittmengen addiert und subtrahiert. Die Kernidee ist, dass bei der einfachen Summation der Mengengrößen Elemente in den Schnittmengen mehrfach gezählt werden.

Für zwei Mengen A und B lautet die Formel einfach: |A∪B| = |A| + |B| − |A∩B|. Die Addition von |A| und |B| zählt Elemente in A∩B doppelt, also subtrahieren wir |A∩B| einmal, um dies auszugleichen.

Die allgemeine Formel für n Mengen

Für n Mengen A₁, A₂, …, A_n lautet die Inklusions-Exklusions-Formel:

|A₁∪…∪A_n| = Σ|A_i| − Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| − … + (−1)ⁿ⁺¹|A₁∩…∩A_n|

Die Summe enthält 2ⁿ−1 Terme (einer für jede nicht-leere Teilmenge). Das Vorzeichen ist positiv für Teilmengen ungerader Größe und negativ für solche gerader Größe.

Die Formel für 3 Mengen

Die am häufigsten verwendete Form ist die Formel für drei Mengen:

|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Here, elements in exactly two sets (z.B., A∩B but not C) are added twice and subtracted once, netting one count. Elements in all three sets are added three times, subtracted three times, and added back once, also netting one count. This confirms the formula counts every element exactly once.

Venn-Diagramme und Bereichszählungen

Ein Venn-Diagramm für n Mengen hat 2ⁿ Bereiche (einschließlich des Äußeren). Für 4 Mengen verwendet man typischerweise Ellipsen, um alle 15 inneren Bereiche darstellen zu können.

Inklusion-Exklusion in der Wahrscheinlichkeitsrechnung

In der Wahrscheinlichkeitstheorie gilt das gleiche Prinzip für Ereigniswahrscheinlichkeiten: P(A∪B∪C) = P(A)+P(B)+P(C) − P(A∩B) − P(A∩C) − P(B∩C) + P(A∩B∩C). Die Wahrscheinlichkeit des Komplements ist 1 − P(A∪B∪C).

Anwendungen des Inklusion-Exklusion-Prinzips

Derangements (Permutationen ohne Fixpunkte): Die Anzahl der derangements D_n wird abgeleitet, indem Inklusion-Exklusion auf die Mengen der Permutationen angewendet wird, die mindestens ein Element festhalten.
Eulersche Phi-Funktion: φ(n) = n × ∏_p|n(1 − 1/p), where the product is over prime factors of n, is derived via inclusion-exclusion over sets of multiples of each prime factor.
Sieb des Eratosthenes: The sieve's counting step is essentially inclusion-exclusion over sets of multiples of small primes.
Bonferroni-Ungleichungen: Truncating the inclusion-exclusion series gives alternating upper and lower bounds on the union size, useful when exact computation is intractable.
Chromatische Polynome: Counting proper colorings of graphs uses inclusion-exclusion over edge sets.
Umfrageanalyse: Computing the number of respondents holding at least one opinion from overlapping survey categories is a direct application.

Rechenbeispiel: Teilbarkeit in 1–100

How many integers from 1 to 100 are divisible by 2, 3, or 5? Let A = multiples of 2 (⌊100/2⌋ = 50), B = multiples of 3 (33), C = multiples of 5 (20). Schnittmengen: A∩B = multiples of 6 (16), A∩C = multiples of 10 (10), B∩C = multiples of 15 (6), A∩B∩C = multiples of 30 (3). By inclusion-exclusion: |A∪B∪C| = 50+33+20−16−10−6+3 = 74. So 26 integers from 1 to 100 are not divisible by 2, 3, or 5.

Schnellreferenztabelle

Sets	Formula Terms	Vorzeichens	Total Terms
2	\|A\|, \|B\|, \|A∩B\|	+, +, −	3
3	Einzelne, Paare, Tripel	+, −, +	7
4	Einzelne, Paare, Tripel, Quadrupel	+, −, +, −	15
n	Alle nicht-leeren Teilmengen	Abwechselnd nach Größe	2ⁿ−1

Häufig gestellte Fragen

Was ist das Inklusions-Exklusions-Prinzip?

Das Prinzip von Inklusion und Exklusion (PIE) ist eine Zähltechnik, die die Größe der Vereinigung überlappender Mengen berechnet, indem abwechselnd Schnittmengengrößen addiert und subtrahiert werden. Das abwechselnde Muster stellt sicher, dass jedes Element genau einmal gezählt wird.

Wie lautet die Formel für die Vereinigung von drei Mengen?

Für drei Mengen A, B und C: |A∪B∪C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. Die drei paarweisen Schnitte werden subtrahiert, und der dreifache Schnitt wird wieder addiert.

Wie wird Inklusion-Exklusion in der Wahrscheinlichkeitsrechnung verwendet?

In der Wahrscheinlichkeitsrechnung gilt die Formel für Ereignisse: P(A∪B∪…) = ΣP(A_i) − ΣP(A_i∩A_j) + …. Wenn eine universelle Mengengröße |U| gegeben ist, konvertiert man Zählungen in Wahrscheinlichkeiten mit P = Zählung / |U|.

Was sind Bonferroni-Ungleichungen?

Bonferroni-Ungleichungen sind Schranken, die durch Abschneiden der Inklusion-Exklusion-Reihe erhalten werden. Das Stoppen nach einem ungeraden Term liefert eine obere Schranke; nach einem geraden Term eine untere Schranke.

Wie hängt Inklusion-Exklusion mit der Eulerschen Phi-Funktion zusammen?

Die Eulersche Phi-Funktion φ(n) zählt die zu n teilerfremden ganzen Zahlen von 1 bis n. Durch Anwendung von Inklusion-Exklusion auf die Mengen der Vielfachen der Primfaktoren erhält man die bekannte Produktformel.

Kann Inklusion-Exklusion für mehr als 4 Mengen verwendet werden?

Ja, das Prinzip lässt sich auf beliebige n Mengen erweitern. Die Formel summiert über alle 2ⁿ−1 nicht-leeren Teilmengen.

Was ist ein Venn-Diagramm?

Ein Venn-Diagramm stellt Mengen als überlappende Formen dar — typischerweise Kreise für 2-3 Mengen und Ellipsen für 4 Mengen. Jeder Bereich entspricht einem einzigartigen Zugehörigkeitsmuster.