www.wikidata.de-de.nina.az

Prinzip von Inklusion und Exklusion Das auch Prinzip der Einschließung und Ausschließung oder Einschluss Ausschluss Verf

Prinzip von Inklusion und Exklusion

Das Prinzip von Inklusion und Exklusion (auch Prinzip der Einschließung und Ausschließung oder Einschluss-Ausschluss-Verfahren) ist eine zur Bestimmung der Mächtigkeit einer Menge hilfreiche Technik. Sie findet vor allem in der Kombinatorik, der Zahlentheorie und der Stochastik Anwendung.

Das Prinzip drückt dazu die Kardinalität einer Ursprungsmenge durch die Kardinalitäten ihrer Teilmengen aus. Diese sind in aller Regel einfacher zu bestimmen. Namensgebend ist dabei das Vorgehen, bei dem zunächst durch die Summe der Größen nicht notwendigerweise disjunkter Teilmengen die Größe von von oben abgeschätzt wird (Inklusion), anschließend jedoch durch die Subtraktion der Größe des gemeinsamen Schnittes der Teilmengen dies wieder zu korrigieren versucht wird (Exklusion).

Das Prinzip Bearbeiten

Prinzip von Inklusion und Exklusion am Beispiel von drei Mengen

Es ist ein bekanntes Ergebnis, dass für je zwei endliche Mengen und

gilt. Hierbei kann man bereits das Prinzip von Inklusion und Exklusion erkennen. Durch wird zunächst die Kardinalität von von oben abgeschätzt. Diese zu hohe Zahl wird anschließend durch die Subtraktion von korrigiert. Zweck dieser Korrektur ist es, diejenigen Elemente einmal wieder abzuziehen, die sowohl in als auch in enthalten sind und somit zunächst doppelt gezählt wurden.

Anhand der nebenstehenden Abbildung lässt sich erkennen, dass eine Verallgemeinerung auf drei endliche Mengen

ergibt.

Im Allgemeinen wollen wir die Kardinalität der Vereinigung von endlichen Mengen

bestimmen. Als erste Näherung erhalten wir durch Inklusion die Summe der Kardinalitäten der . Diese Summe kann jedoch zu groß sein, da wir Elemente aus dem Schnitt zweier Mengen mehrfach zählen würden, es gilt also

Um dies zu korrigieren, können wir nun durch Exklusion die Summe der Kardinalitäten der Schnittmengen aller Mengenpaare wieder abziehen. Dann gilt

Denn Elemente des Schnittes dreier Mengen würden – obwohl nur zweimal zu häufig bei der Inklusion mitgezählt – durch , durch und durch dreimal wieder abgezogen. Dies nun durch Inklusion, also durch Addition der Summe der Größe aller Schnitte aus drei Mengen, zu korrigieren, ergibt

Darauf folgt durch Exklusion

und so weiter, wobei beispielsweise bedeutet, dass über alle geordneten Tripel summiert wird, die den Ungleichungen genügen.

Satz Bearbeiten

Es lässt sich folgende allgemeine Aussage beweisen.

Gegeben sei eine endliche Menge , die sich als Vereinigung von Teilmengen schreiben lässt, d. h. . Es bezeichne im Folgenden zu einer Indexmenge die Menge den Schnitt über alle durch die Elemente der Indexmenge bezeichneten Teilmengen, also:

Dann gilt:

oder gleichwertig auch

Mit anderen Worten: Betrachtet man alle möglichen Schnitte (außer dem leeren Schnitt ), so ist die Kardinalität von gleich der Summe der Kardinalität aller Schnitte einer ungeraden Anzahl an Teilmengen (Inklusion) minus der Summe der Kardinalität aller Schnitte einer geraden Anzahl an Teilmengen (Exklusion), formal:

Anwendung Bearbeiten

Eine Anwendung des Prinzips liefert die Siebformel von Poincaré und Sylvester, auch Additionssatz für Wahrscheinlichkeiten genannt:

Für die Wahrscheinlichkeit von beliebigen Ereignissen aus einem Wahrscheinlichkeitsraum gilt:

Wegen der Additivität von Maßen lässt sich der oben angegebene heuristische Beweis für das Prinzip von Inklusion und Exklusion, der mit Mitteln der elementaren Mengentheorie geführt wurde, direkt auf Wahrscheinlichkeiten übertragen.

Beispielsweise gilt für drei Ereignisse , und stets

Allgemein gilt diese Aussage auch schon für endliche Inhalte auf Ringen.

Beispiel Bearbeiten

Beim vorweihnachtlichen Brauch des Wichtelns beschenkt sich eine Gruppe gegenseitig. Jeder beschenkt genau eine Person und wird wiederum von genau einer Person beschenkt. Dabei wird per Los zufällig festgelegt, wer welches Geschenk erhält. Idealerweise sollte jeder das Geschenk eines anderen erhalten. Es kann jedoch passieren, dass jemand zufällig sein eigenes Geschenk bekommt. Für die betreffende Person wäre es mit der Überraschung vorbei. Doch wie wahrscheinlich ist dieser Fall bei einer Gruppe von Personen?

Mathematisch ausgedrückt möchte man die Wahrscheinlichkeit des Ereignisses A := „Mindestens eine Person erhält ihr eigenes Geschenk“ ermitteln. Dies ist äquivalent dazu, dass mindestens eines der Ereignisse Ai := „Person i erhält ihr eigenes Geschenk“ für zutrifft, wobei die Anzahl Personen ist, die am Wichteln teilnimmt. Der rechte Term der Siebformel

kann vereinfacht werden zu

da in diesem Beispiel die Wahrscheinlichkeiten aller Schnittmengen mit derselben Anzahl an Teilmengen gleich sind. Die Wahrscheinlichkeit, dass bestimmte Personen jeweils ihre eigenen Geschenke ziehen, beträgt

Mit Hilfe der Definition des Binomialkoeffizienten erhält man somit

Nach dem Kürzen der Brüche ergibt sich

Mit der Summenschreibweise lässt sich das verkürzt als ausdrücken.

Bei großen Gruppen müssen ziemlich viele Summanden addiert werden und die Fakultät wird schnell extrem groß. In diesem Fall ist es zweckmäßig, den Grenzwert dieser Summe für zu bilden:

Bei der Reihe handelt es sich um die Auswertung der Taylorreihe mit Entwicklungsstelle der natürlichen Exponentialfunktion an der Stelle , weshalb sich die Lösung auf insgesamt vereinfacht. Dieser Wert kann als Näherung für großes betrachtet werden. In großen Gruppen beträgt die Wahrscheinlichkeit demnach etwa , dass mindestens eine Person ihr eigenes Geschenk erhält.

Siehe auch Bearbeiten

Weblinks Bearbeiten

Wikiversity: Eine Vorlesung über die Siebformel im Rahmen eines Kurses zur diskreten Mathematik – Kursmaterialien

Literatur Bearbeiten

  • Norbert Henze: Stochastik für Einsteiger. Eine Einführung in die faszinierende Welt des Zufalls. Springer Spektrum, 10. Auflage, Wiesbaden 2016, S. 70–76.
  • Klaus Dohmen: Improved Bonferroni Inequalities via Abstract Tubes – Inequalities and Identities of Inclusion-Exclusion Type. Springer-Verlag, 2003, ISBN 3-540-20025-8.
  • Stasys Jukna: Extremal Combinatorics. Springer, Mai 2001, ISBN 3-540-66313-4.

Einzelnachweise Bearbeiten

  1. Sinngemäß in leicht anderer Einkleidung in: Norbert Henze: Stochastik für Einsteiger. Eine Einführung in die faszinierende Welt des Zufalls. Springer Spektrum, 1. Auflage, Wiesbaden 1997, S. 74–77.
  2. Stefan Bartz: Selbst-Bewichtelungen in 2 von 3 Spielen. In: Stochastik in der Schule. Nr. 33, 2013 (stefanbartz.de [PDF; 684 kB]).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Prinzip von Inklusion und Exklusion auch Prinzip der Einschliessung und Ausschliessung oder Einschluss Ausschluss Verfahren ist eine zur Bestimmung der Machtigkeit einer Menge hilfreiche Technik Sie findet vor allem in der Kombinatorik der Zahlentheorie und der Stochastik Anwendung Das Prinzip druckt dazu die Kardinalitat einer Ursprungsmenge X displaystyle X durch die Kardinalitaten ihrer Teilmengen aus Diese sind in aller Regel einfacher zu bestimmen Namensgebend ist dabei das Vorgehen bei dem zunachst durch die Summe der Grossen nicht notwendigerweise disjunkter Teilmengen die Grosse von X displaystyle X von oben abgeschatzt wird Inklusion anschliessend jedoch durch die Subtraktion der Grosse des gemeinsamen Schnittes der Teilmengen dies wieder zu korrigieren versucht wird Exklusion Inhaltsverzeichnis 1 Das Prinzip 2 Satz 3 Anwendung 4 Beispiel 5 Siehe auch 6 Weblinks 7 Literatur 8 EinzelnachweiseDas Prinzip Bearbeiten nbsp Prinzip von Inklusion und Exklusion am Beispiel von drei MengenEs ist ein bekanntes Ergebnis dass fur je zwei endliche Mengen A displaystyle A nbsp und B displaystyle B nbsp A B A B A B displaystyle A cup B A B A cap B nbsp gilt Hierbei kann man bereits das Prinzip von Inklusion und Exklusion erkennen Durch A B displaystyle A B nbsp wird zunachst die Kardinalitat von A B displaystyle A cup B nbsp von oben abgeschatzt Diese zu hohe Zahl wird anschliessend durch die Subtraktion von A B displaystyle A cap B nbsp korrigiert Zweck dieser Korrektur ist es diejenigen Elemente einmal wieder abzuziehen die sowohl in A displaystyle A nbsp als auch in B displaystyle B nbsp enthalten sind und somit zunachst doppelt gezahlt wurden Anhand der nebenstehenden Abbildung lasst sich erkennen dass eine Verallgemeinerung auf drei endliche Mengen A B C A B C A B A C B C A B C displaystyle A cup B cup C A B C A cap B A cap C B cap C A cap B cap C nbsp ergibt Im Allgemeinen wollen wir die Kardinalitat der Vereinigung von n displaystyle n nbsp endlichen Mengen X A 1 A 2 A n displaystyle X A 1 cup A 2 cup dotsb cup A n nbsp bestimmen Als erste Naherung erhalten wir durch Inklusion die Summe der Kardinalitaten der A i displaystyle A i nbsp Diese Summe kann jedoch zu gross sein da wir Elemente aus dem Schnitt zweier Mengen A i A j displaystyle A i cap A j nbsp mehrfach zahlen wurden es gilt also X 1 i n A i displaystyle X leq sum 1 leq i leq n A i nbsp Um dies zu korrigieren konnen wir nun durch Exklusion die Summe der Kardinalitaten der Schnittmengen aller Mengenpaare wieder abziehen Dann gilt X 1 i n A i 1 i lt j n A i A j displaystyle X geq sum 1 leq i leq n A i sum 1 leq i lt j leq n A i cap A j nbsp Denn Elemente des Schnittes dreier Mengen A i A j A k displaystyle A i cap A j cap A k nbsp wurden obwohl nur zweimal zu haufig bei der Inklusion mitgezahlt durch A i A j displaystyle A i cap A j nbsp durch A i A k displaystyle A i cap A k nbsp und durch A j A k displaystyle A j cap A k nbsp dreimal wieder abgezogen Dies nun durch Inklusion also durch Addition der Summe der Grosse aller Schnitte aus drei Mengen zu korrigieren ergibt X 1 i n A i 1 i lt j n A i A j 1 i lt j lt k n A i A j A k displaystyle X leq sum 1 leq i leq n A i sum 1 leq i lt j leq n A i cap A j sum 1 leq i lt j lt k leq n A i cap A j cap A k nbsp Darauf folgt durch Exklusion X 1 i n A i 1 i lt j n A i A j 1 i lt j lt k n A i A j A k 1 i lt j lt k lt l n A i A j A k A l displaystyle X geq sum 1 leq i leq n A i sum 1 leq i lt j leq n A i cap A j sum 1 leq i lt j lt k leq n A i cap A j cap A k sum 1 leq i lt j lt k lt l leq n A i cap A j cap A k cap A l nbsp und so weiter wobei beispielsweise 1 i lt j lt k n displaystyle sum 1 leq i lt j lt k leq n nbsp bedeutet dass uber alle geordneten Tripel i j k displaystyle i j k nbsp summiert wird die den Ungleichungen 1 i lt j lt k n displaystyle 1 leq i lt j lt k leq n nbsp genugen Satz BearbeitenEs lasst sich folgende allgemeine Aussage beweisen Gegeben sei eine endliche Menge X displaystyle X nbsp die sich als Vereinigung von n displaystyle n nbsp Teilmengen A 1 A 2 A n displaystyle A 1 A 2 dotsc A n nbsp schreiben lasst d h X i 1 n A i displaystyle X bigcup i 1 n A i nbsp Es bezeichne im Folgenden zu einer Indexmenge I 1 2 n displaystyle I subseteq 1 2 dotsc n nbsp die Menge A I displaystyle A I nbsp den Schnitt uber alle durch die Elemente der Indexmenge bezeichneten Teilmengen also A I i I A i displaystyle A I bigcap i in I A i nbsp mit dem Spezialfall A X displaystyle A emptyset X nbsp Dann gilt X I 1 n 1 I 1 A I displaystyle X sum emptyset not I subseteq 1 dotsc n left 1 right I 1 A I nbsp oder gleichwertig auch I 1 n 1 I 1 A I 0 displaystyle sum I subseteq 1 dotsc n left 1 right I 1 A I 0 nbsp Mit anderen Worten Betrachtet man alle moglichen Schnitte A I displaystyle A I nbsp ausser dem leeren Schnitt A displaystyle A emptyset nbsp so ist die Kardinalitat von X displaystyle X nbsp gleich der Summe der Kardinalitat aller Schnitte einer ungeraden Anzahl an Teilmengen Inklusion minus der Summe der Kardinalitat aller Schnitte einer geraden Anzahl an Teilmengen Exklusion formal X I 1 n I ungerade A I I 1 n I gerade A I displaystyle X sum I subseteq 1 dotsc n atop I text ungerade A I sum emptyset not I subseteq 1 dotsc n atop I text gerade A I nbsp Anwendung BearbeitenEine Anwendung des Prinzips liefert die Siebformel von Poincare und Sylvester auch Additionssatz fur Wahrscheinlichkeiten genannt Fur die Wahrscheinlichkeit von beliebigen Ereignissen A i displaystyle A i nbsp aus einem Wahrscheinlichkeitsraum W S P displaystyle Omega Sigma P nbsp gilt P i 1 n A i k 1 n 1 k 1 I 1 n I k P i I A i displaystyle P left bigcup i 1 n A i right sum k 1 n left 1 k 1 sum I subseteq 1 dotsc n atop I k P left bigcap i in I A i right right nbsp Wegen der Additivitat von Massen lasst sich der oben angegebene heuristische Beweis fur das Prinzip von Inklusion und Exklusion der mit Mitteln der elementaren Mengentheorie gefuhrt wurde direkt auf Wahrscheinlichkeiten ubertragen Beispielsweise gilt fur drei Ereignisse A displaystyle A nbsp B displaystyle B nbsp und C displaystyle C nbsp stets P A B C P A P B P C P A B P A C P B C P A B C displaystyle P A cup B cup C P A P B P C P A cap B P A cap C P B cap C P A cap B cap C nbsp Allgemein gilt diese Aussage auch schon fur endliche Inhalte auf Ringen Beispiel Bearbeiten Hauptartikel Fixpunktfreie Permutation Beim vorweihnachtlichen Brauch des Wichtelns beschenkt sich eine Gruppe gegenseitig Jeder beschenkt genau eine Person und wird wiederum von genau einer Person beschenkt Dabei wird per Los zufallig festgelegt wer welches Geschenk erhalt Idealerweise sollte jeder das Geschenk eines anderen erhalten Es kann jedoch passieren dass jemand zufallig sein eigenes Geschenk bekommt Fur die betreffende Person ware es mit der Uberraschung vorbei Doch wie wahrscheinlich ist dieser Fall bei einer Gruppe von n displaystyle n nbsp Personen Mathematisch ausgedruckt mochte man die Wahrscheinlichkeit des Ereignisses A Mindestens eine Person erhalt ihr eigenes Geschenk ermitteln Dies ist aquivalent dazu dass mindestens eines der Ereignisse Ai Person i erhalt ihr eigenes Geschenk fur i 1 n displaystyle i in 1 dotsc n nbsp zutrifft wobei n displaystyle n nbsp die Anzahl Personen ist die am Wichteln teilnimmt Der rechte Term der Siebformel P i 1 n A i k 1 n 1 k 1 I 1 n I k P i I A i displaystyle P left bigcup i 1 n A i right sum k 1 n left 1 k 1 sum I subseteq 1 dotsc n atop I k P left bigcap i in I A i right right nbsp kann vereinfacht werden zu n P A 1 n 2 P A 1 A 2 n 3 P A 1 A 2 A 3 n 4 P A 1 A 2 A 3 A 4 displaystyle nP A 1 binom n 2 P A 1 cap A 2 binom n 3 P A 1 cap A 2 cap A 3 binom n 4 P A 1 cap A 2 cap A 3 cap A 4 nbsp n 5 P A 1 A 2 A 3 A 4 A 5 1 n 1 P A 1 A n displaystyle binom n 5 P A 1 cap A 2 cap A 3 cap A 4 cap A 5 dotsb dotsb 1 n 1 P A 1 cap dotsb cap A n nbsp dd da in diesem Beispiel die Wahrscheinlichkeiten aller Schnittmengen mit derselben Anzahl an Teilmengen gleich sind Die Wahrscheinlichkeit dass k displaystyle k nbsp bestimmte Personen jeweils ihre eigenen Geschenke ziehen betragt P A 1 A 2 A 3 A k 1 n n 1 n 2 n k 1 displaystyle P A 1 cap A 2 cap A 3 cap dotsb cap A k frac 1 n cdot n 1 cdot n 2 cdot dotsm cdot n k 1 nbsp Mit Hilfe der Definition des Binomialkoeffizienten erhalt man somit P A 1 A n n 1 n n n 1 1 2 1 n n 1 n n 1 n 2 1 2 3 1 n n 1 n 2 displaystyle P A 1 cup dotsb cup A n n cdot frac 1 n frac n n 1 1 cdot 2 cdot frac 1 n n 1 frac n n 1 n 2 1 cdot 2 cdot 3 cdot frac 1 n n 1 n 2 nbsp n n 1 n 2 n 3 1 2 3 4 1 n n 1 n 2 n 3 n n 1 n 2 n 3 n 4 1 2 3 4 5 1 n n 1 n 2 n 3 n 4 displaystyle frac n n 1 n 2 n 3 1 cdot 2 cdot 3 cdot 4 cdot frac 1 n n 1 n 2 n 3 frac n n 1 n 2 n 3 n 4 1 cdot 2 cdot 3 cdot 4 cdot 5 cdot frac 1 n n 1 n 2 n 3 n 4 nbsp 1 n 1 1 1 2 3 n displaystyle dotsb dotsb dotsb dotsb 1 n 1 cdot frac 1 1 cdot 2 cdot 3 cdot dotsm cdot n nbsp dd Nach dem Kurzen der Bruche ergibt sich P A 1 A n 1 1 1 2 1 1 2 3 1 1 2 3 4 1 1 2 3 4 5 1 n 1 1 1 2 3 n displaystyle P A 1 cup dotsb cup A n 1 frac 1 1 cdot 2 frac 1 1 cdot 2 cdot 3 frac 1 1 cdot 2 cdot 3 cdot 4 frac 1 1 cdot 2 cdot 3 cdot 4 cdot 5 dotsb dotsb dotsb dotsb 1 n 1 cdot frac 1 1 cdot 2 cdot 3 cdot dotsm cdot n nbsp Mit der Summenschreibweise lasst sich das verkurzt als P A 1 A n 1 k 0 n 1 k k displaystyle P A 1 cup dotsb cup A n 1 sum k 0 n frac 1 k k nbsp ausdrucken Bei grossen Gruppen mussen ziemlich viele Summanden addiert werden und die Fakultat k displaystyle k nbsp wird schnell extrem gross In diesem Fall ist es zweckmassig den Grenzwert dieser Summe fur n displaystyle n to infty nbsp zu bilden lim n 1 k 0 n 1 k k 1 k 0 1 k k 1 e 1 1 1 e 63 2 displaystyle lim n to infty left 1 sum k 0 n frac 1 k k right 1 sum k 0 infty frac 1 k k 1 e 1 1 frac 1 e approx 63 2 nbsp Bei der Reihe handelt es sich um die Auswertung der Taylorreihe mit Entwicklungsstelle 0 displaystyle 0 nbsp der naturlichen Exponentialfunktion an der Stelle x 1 displaystyle x 1 nbsp weshalb sich die Losung auf insgesamt 1 1 e displaystyle 1 frac 1 e nbsp vereinfacht Dieser Wert kann als Naherung fur grosses n displaystyle n nbsp betrachtet werden In grossen Gruppen betragt die Wahrscheinlichkeit demnach etwa 63 2 displaystyle 63 2 nbsp dass mindestens eine Person ihr eigenes Geschenk erhalt 1 2 Siehe auch BearbeitenBonferroni Ungleichung SchubfachprinzipWeblinks Bearbeiten nbsp Wikiversity Eine Vorlesung uber die Siebformel im Rahmen eines Kurses zur diskreten Mathematik KursmaterialienLiteratur BearbeitenNorbert Henze Stochastik fur Einsteiger Eine Einfuhrung in die faszinierende Welt des Zufalls Springer Spektrum 10 Auflage Wiesbaden 2016 S 70 76 Klaus Dohmen Improved Bonferroni Inequalities via Abstract Tubes Inequalities and Identities of Inclusion Exclusion Type Springer Verlag 2003 ISBN 3 540 20025 8 Stasys Jukna Extremal Combinatorics Springer Mai 2001 ISBN 3 540 66313 4 Einzelnachweise Bearbeiten Sinngemass in leicht anderer Einkleidung in Norbert Henze Stochastik fur Einsteiger Eine Einfuhrung in die faszinierende Welt des Zufalls Springer Spektrum 1 Auflage Wiesbaden 1997 S 74 77 Stefan Bartz Selbst Bewichtelungen in 2 von 3 Spielen In Stochastik in der Schule Nr 33 2013 stefanbartz de PDF 684 kB Abgerufen von https de wikipedia org w index php title Prinzip von Inklusion und Exklusion amp oldid 233817399