Inklusions-Exklusions-Rechner

Inklusions-Exklusions-Rechner

Der Inklusions-Exklusions-Rechner berechnet die Größe der Vereinigung endlicher Mengen, |A₁ ∪ A₂ ∪ … ∪ A_n|, unter Verwendung des Inklusions-Exklusions-Prinzips — einer der am häufigsten verwendeten Identitäten in der Kombinatorik und diskreten Wahrscheinlichkeit. Geben Sie rohe Mengenelemente oder einfach die bekannten Kardinalitäten jeder Schnittmenge ein, und der Rechner liefert die Größe der Vereinigung, die vollständige vorzeichenbehaftete Erweiterung, die Größen jeder disjunkten Venn-Region sowie ein Live-Diagramm — für jeweils 2 bis 5 Mengen.

Das Inklusions-Exklusions-Prinzip

Bei zwei endlichen Mengen A und B führt das Addieren ihrer Größen dazu, dass Elemente, die in beiden enthalten sind, doppelt gezählt werden. Das Subtrahieren der Schnittmenge korrigiert diese Doppelzählung:

Bei drei Mengen entfernt das Subtrahieren jeder paarweisen Schnittmenge die dreifache Zählung zweimal, weshalb wir die dreifache Schnittmenge wieder addieren:

Allgemein alternieren bei n Mengen die Vorzeichen abhängig von der Anzahl der Mengen in der jeweiligen Schnittmenge:

Es gibt 2ⁿ − 1 nicht-leere Teilmengen von {1, …, n}, daher hat die Formel 3 Terme für 2 Mengen, 7 für 3 Mengen, 15 für 4 Mengen und 31 für 5 Mengen. Der Rechner wertet jeden Term einzeln aus und zeigt dessen Vorzeichen an, damit Sie die Herleitung nachvollziehen können.

Zwei Eingabemodi

Wählen Sie den Modus, der zu Ihren Daten passt. Die meisten Textaufgaben geben Kardinalitäten direkt an; Programmieraufgaben liefern meist die Mengen selbst.

Im Kardinalitäten-Modus wird jede ausgelassene Schnittmenge als Null angenommen. Akzeptierte Trennzeichen für Schnittmengen-Labels sind A∩B, A&B und AB, optional mit Betragsstrichen (|A∩B|).

Größen disjunkter Regionen — Möbius-Inversion

Zusätzlich zur Größe der Vereinigung liefert der Rechner die Größe jeder disjunkten Region des Venn-Diagramms. Die Region „nur in A und B, aber nicht in C“ zählt Elemente, die genau zu diesen Mengen gehören. Die Summe der Größen aller disjunkten Regionen entspricht der Vereinigung, was eine sofortige Plausibilitätsprüfung ermöglicht.

Dies ist das Möbius-Inversions-Dual zur Inklusion-Exklusion. Zum Beispiel bei drei Mengen:

Falls Sie inkonsistente Kardinalitäten eingeben — zum Beispiel |A∩B| > |A| — weist der Rechner die Eingabe ab. Wenn die Einzelgrößen stimmen, die kombinierten Werte aber dennoch nicht von realen Mengen stammen können, werden eine oder mehrere Regionen negativ, was als Warnung markiert wird.

Praxisbeispiel — Klassen-Umfrage mit 3 Mengen

In einer Klasse mit 100 Schülern wird gefragt, welche Sportarten sie betreiben. 50 spielen Fußball (A), 40 Basketball (B), 30 Tennis (C). 15 spielen A und B, 10 spielen A und C, 8 spielen B und C, und 3 spielen alle drei. Wie viele spielen mindestens eine Sportart?

Somit betreiben 90 von 100 Schülern mindestens eine dieser Sportarten; 10 betreiben keine. Die Regionsaufschlüsselung verrät mehr: 28 spielen nur Fußball, 20 nur Basketball, 15 nur Tennis, 12 spielen Fußball und Basketball, aber nicht Tennis, und so weiter.

So verwenden Sie diesen Rechner

1. Eingabemodus wählen — Elemente, wenn Sie die einzelnen Objekte haben; Kardinalitäten, wenn Sie nur Größen kennen.
2. Daten eingeben im Textbereich, eine Zeile pro Menge oder eine Zeile pro bekannter Kardinalität.
3. Anzahl der Mengen wählen (2 bis 5) im Kardinalitäten-Modus. Im Elemente-Modus wird die Anzahl automatisch erkannt.
4. Auf Vereinigung & Regionen berechnen klicken. Das Ergebnis zeigt |⋃ Aᵢ| in einer Hero-Card, die vollständige Inklusions-Exklusions-Erweiterung mit jedem vorzeichenbehafteten Term, ein Venn-Diagramm-SVG (für 2, 3 oder 4 Mengen) und eine Tabelle mit jeder disjunkten Region und ihrer Größe.
5. Hovern Sie über eine Venn-Region oder eine Tabellenzeile, um den entsprechenden Eintrag hervorzuheben — ein schneller visueller Beweis, dass Tabelle und Diagramm die gleiche Zerlegung darstellen.

Häufige Anwendungen

• Kombinatorik — Zählen von Derangements (Fixpunktfreie Permutationen), Surjektionen, Permutationen mit verbotenen Positionen.
• Wahrscheinlichkeit — P(A ∪ B ∪ C) für Ereignisse, Boolesche Ungleichung, Geburtstagsparadoxon.
• Zahlentheorie — Zählen von Zahlen, die teilerfremd zu einem Produkt sind, mittels Eulerscher Phi-Funktion: die φ-Formel basiert rein auf Inklusion-Exklusion.
• Umfrage-Analyse — Fragen des Typs „Wie viele Befragte gehören mindestens einer Kategorie an“.
• Datenbank-Abfragen — Schätzung der Größe von UNION-Operationen basierend auf COUNT-Werten von INTERSECT-Mengen.
• Informatik — Siebalgorithmen, Kardinalitätsschätzung bei Bitmap-Indizes, Zählen von Reichweiten gemäß DSGVO/HIPAA.

Tipps & häufige Fehler

• Vergessen Sie nicht, die dreifache Schnittmenge wieder zu addieren. Der häufigste Fehler bei 3-Mengen-Aufgaben ist das Aufhören nach dem Subtrahieren der Paare, was zu einem zu kleinen Ergebnis führt.
• Fehlend ≠ Null bei realen Mengen. Im Kardinalitäten-Modus wird eine ausgelassene Schnittmenge als Null gewertet. Wenn in Ihrer Aufgabe nicht steht, dass eine Schnittmenge leer ist, müssen Sie sie wahrscheinlich angeben.
• Jede Schnittmenge ≤ jede enthaltene Menge. |A ∩ B| kann niemals größer als min(|A|, |B|) sein. Der Rechner weist unmögliche Eingaben sofort zurück.
• Nutzen Sie den Elemente-Modus, wann immer möglich. Er eliminiert die Fehlerquelle „Habe ich alle Schnittmengen korrekt eingegeben?“, da er diese direkt aus den Mengen ableitet.

Häufig gestellte Fragen

Was ist das Inklusions-Exklusions-Prinzip?

Das Inklusions-Exklusions-Prinzip ist eine Identität zur Bestimmung der Größe der Vereinigung von Mengen basierend auf den Größen der Mengen selbst und ihrer Schnittmengen. Für zwei Mengen gilt |A ∪ B| = |A| + |B| − |A ∩ B|. Bei drei Mengen wird eine Korrektur für die dreifache Schnittmenge addiert, und bei n Mengen alternieren die Vorzeichen: Mengen addieren, Paare subtrahieren, Tripel addieren usw.

Was ist der Unterschied zwischen dem Elemente- und dem Kardinalitäten-Modus?

Der Elemente-Modus erwartet die tatsächlichen Elemente jeder Menge, eine Zeile pro Menge, und der Rechner findet jede Schnittmenge automatisch. Der Kardinalitäten-Modus erwartet nur die Größen der Mengen und ihrer Schnittmengen. Er ist ideal für Textaufgaben, bei denen man weiß, wie viele Personen Tee, Kaffee oder beides mögen, ohne die tatsächlichen Namen zu kennen.

Warum zeigt mein Rechner negative Regionsgrößen an?

Negative Regionsgrößen im Kardinalitäten-Modus bedeuten, dass Ihre Eingaben inkonsistent sind — keine Sammlung realer Mengen kann solche Schnittmengengrößen haben. Meist passiert dies, wenn eine paarweise oder dreifache Schnittmenge größer ist, als die einzelnen Mengen zulassen. Überprüfen Sie die Zahlen; jede Schnittmenge muss kleiner oder gleich jeder der Mengen sein, in denen sie enthalten ist.

Wie viele Mengen kann dieser Rechner verarbeiten?

Der Rechner unterstützt 2 bis 5 Mengen. Das Venn-Diagramm wird für 2, 3 und 4 Mengen gerendert; die Tabelle mit der Regionsaufschlüsselung wird für jede Anzahl von Mengen bis 5 angezeigt. Bei größeren Problemen wird die Inklusions-Exklusions-Erweiterung unübersichtlich, weshalb die meisten Aufgaben bei 4 oder 5 Mengen aufhören.

Was ist eine disjunkte Region?

Eine disjunkte Region ist ein Teil des Venn-Diagramms, der genau zu einer Kombination von Mengen gehört und zu keiner anderen. Bei drei Mengen A, B, C gibt es sieben nicht-leere Regionen: nur-A, nur-B, nur-C, nur-A∩B, nur-A∩C, nur-B∩C und A∩B∩C. Ihre Größen ergeben in der Summe |A ∪ B ∪ C|, was ein schneller Weg zur Überprüfung der Berechnung ist.

Kann ich den Rechner für unendliche oder kontinuierliche Mengen verwenden?

Der Rechner ist für endliche Mengen konzipiert, deren Größen nicht-negative ganze Zahlen sind. Für Wahrscheinlichkeits- oder Maßtheorie-Probleme mit kontinuierlichen Mengen können Sie die Inklusions-Exklusions-Identität zwar konzeptionell anwenden, das numerische Tool erwartet jedoch Kardinalitäten als ganze Zahlen.

Weiterführende Informationen

• Prinzip von Inklusion und Exklusion — Wikipedia
• Venn-Diagramm — Wikipedia
• Möbius-Inversionsformel — Wikipedia
• Derangements (eine klassische IE-Anwendung) — Wikipedia

Andere verwandte Tools:

Erweiterte Rechenoperationen:

• Antilogarithmus Rechner
• Betafunktion-Rechner
• Binomialkoeffizient-Rechner
• Binomialverteilungsrechner
• Binär-Rechner Empfohlen
• Zentraler Grenzwertsatz Rechner
• Kombinatorik-Rechner
• Rechner für komplementäre Fehlerfunktion
• Komplexe Zahlen Rechner Empfohlen
• Entropie-Rechner
• Fehlerfunktion berechnen
• Rechner für exponentiellen Zerfall
• Exponentielle Zunahme Rechner
• Exponentielles Integral Rechner
• exponenten-rechner-hohe-präzision
• Fakultätsrechner
• Gammafunktion-Rechner
• Goldener Schnitt Rechner
• Halbwertszeit berechnen
• Prozentuale Wachstumsrate Rechner Empfohlen
• permutationsrechner
• Poisson-Verteilungsrechner
• Polynom Wurzeln Rechner mit detaillierten Schritten
• Wahrscheinlichkeitsrechner
• Wahrscheinlichkeitsverteilung Rechner
• Anteil-Rechner
• Mitternachtsformel Rechner
• Wissenschaftlicher Taschenrechner
• Wissenschaftliche Schreibweise Rechner
• Signifikante Stellen Rechner Neu
• Summe von Kuben Rechner
• Summe von positiven Ganzzahlen Rechner
• Summe von Quadratzahlen Rechner
• Wahrheitstabellen-Generator
• Mengenlehre-Rechner
• Venn-Diagramm-Generator (3 Mengen)
• Chinesischer Restsatz Rechner
• Euler Totient Funktion Rechner
• Erweiterter Euklidischer Algorithmus Rechner
• Modularer Multiplikativer Inverser Rechner
• Kettenbruch-Rechner
• Dijkstra Kürzester Weg Rechner
• Minimaler Spannbaum Rechner
• Graph Gradfolgen-Validator
• Derangement Subfaktorielle Rechner
• Stirling-Zahlen-Rechner
• Schubfachprinzip-Rechner
• Markov-Ketten Stationäre Verteilung Rechner
• rundungsrechner Neu
• Negativer Binomialverteilungsrechner Neu
• Permutationen mit Wiederholung Rechner Neu
• Modulare Exponentiationsrechner Neu
• Primitivwurzel-Rechner
• Boolesche Algebra Vereinfacher Neu
• Karnaugh-Diagramm (K-Map) Löser Neu
• Graphfärbung Rechner Neu
• Topologische Sortierung Rechner Neu
• Adjazenzmatrix-Rechner Neu
• Inklusions-Exklusions-Rechner Neu
• Solver für lineare Programmierung Neu
• Traveling Salesman Solver (TSP) Neu
• Hamilton-Pfad-Prüfer Neu
• Planarer Graph Prüfer Neu
• Netzwerkfluss-Rechner (Maximaler Fluss) Neu
• Stable Marriage Problem Löser Neu
• Gruppentheorie-Ordnungsrechner Neu
• Ring und Körperrechner Neu