Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 3/kontrolle
- Die Siebformel
Die Siebformel berechnet die Anzahl in einer Vereinigung von Mengen, wenn die einzelnen Anzahlen der Mengen und ihrer Durchschnitte bekannt sind. Im einfachsten Fall, bei
ist
Um die Elemente, die sowohl in als auch in sind, nicht doppelt zu zählen, muss man deren Anzahl abziehen.
Bei drei Mengen
ist
Wir beweisen die Aussage durch Induktion über , wobei der Fall klar ist. Für siehe Aufgabe 1.18. Es ist
wobei wir für die zweite Gleichung den Fall von zwei Teilmengen und für die dritte und die vierte Gleichung die Induktionsvoraussetzung verwendet haben. Für die fünfte Gleichung führen wir hinten die Indexverschiebung durch und der mittlere Term wird in die rechte Summe integriert. Die sechste Gleichung ergibt sich von unten nach oben gelesen, wenn man die Teilmengen
je nachdem aufspaltet, ob dazu gehört oder nicht.
Man spricht auch vom Prinzip der Inklusion und Exklusion. Wir geben noch einen zweiten Beweis für die vorstehende Aussage.
Beide Seiten der Siebformel verhalten sich additiv, wenn eine disjunkte Zerlegung der Grundmenge vorliegt. Deshalb genügt es, die Aussage für eine einelementige Menge zu zeigen (man fragt sich für jedes Element, wie oft es links und wie oft es rechts gezählt wird). Sei also . Dann gibt es für die Teilmengen nur die Möglichkeiten oder . Wir können annehmen, dass
und
ist. Zu einer Teilmenge ist dann einelementig genau dann, wenn ist, und sonst immer leer. Daher ist die rechte Seite gleich
Dies ist bei gleich und sonst nach Aufgabe 3.2 gleich , was mit der linken Seite übereinstimmt.
Die Bezeichnung „Siebformel“ kann man sich folgendermaßen erklären: Es sei eine Menge von Sandkörnern, Kristallen oder Diamanten gegeben, die unterschiedliche Größen und Formen besitzen. Es sei eine Menge von Sieben gegeben, mit denen man den Sand sieben möchte. Dann ist die Menge der Sandkörner, die durch das Sieb durchfallen, und zu einer Teilmenge ist dann die Menge der Sandkörner, die durch die Siebe , , (wenn man sie übereinander hält) durchfallen.
Als eine erste Anwendung der Siebformel besprechen wir fixpunktfreie Permutationen.
- Fixpunktefreie Permutationen
Eine gewisse Gruppe von Personen möchte wichteln. D.h. jeder Person wird eine weitere Person zugelost, die die erste Person beschenken soll, und dabei wird größtmögliche Geheimhaltung angestrebt. Typischerweise legt man die Zuordnung so fest, dass man die Namen der beteiligten Personen einzeln auf einen Zettel schreibt und dann die Leute ziehen lässt. Die ziehende Person beschenkt die Person, deren Namen auf dem gezogenen Zettel steht. Wenn eine Person sich selbst zieht, so hat man ein Problem. Die übliche praktische Lösung ist, alles zurück in den Topf zu werfen und nochmal probieren, solange, bis es keine Selbstziehungen mehr gibt.
Wir wollen verstehen, wie hoch die Wahrscheinlichkeit ist, dass sich jemand bei einer Ziehung selbst zieht, und daher das Ganze wiederholt werden muss. Insbesondere wollen wir die Asymptotik verstehen, wenn die Anzahl der beteiligten Personen sehr groß ist bzw. wird.
Wir erinnern an das Konzept eines Fixpunktes.
Es geht also um die fixpunktfreien Permutationen. Es sei die Anzahl der Personen, die wichteln möchten.
Hier gibt es nur eine Ziehung, die eine Person zieht sich selbst, dies ist unvermeidbar. Die Wahrscheinlichkeit, dass eine (erlaubte) Wichtelzuordnung gezogen wird, ist also , und die Wahrscheinlichkeit, dass eine Nichtwichtelzuordnung gezogen wird, ist .
Nennen wir die Personen und . Hier gibt es zwei Ziehmöglichkeiten, nämlich
und
Die erste Möglichkeit ist die Identität, die zweite die Vertauschung. Die erste ist nicht erlaubt, die zweite ist eine erlaubte Wichtelzuordnung. Die Wahrscheinlichkeit is also .
Nennen wir die Personen und . Hier gibt es sechs Ziehmöglichkeiten, nämlich
Von den sechs Möglichkeiten sind nur die vierte und die fünfte ohne Selbstziehung (ohne Fixpunkt). Die Wahrscheinlichkeit für eine fixpunktfreie Ziehung ist demnach .
Nennen wir die Personen und . Wir wissen, dass es insgesamt Permutationen gibt. Alle aufzulisten und einfach zu schauen, welche einen Fixpunkt haben und welche nicht, ist schon ziemlich aufwändig, siehe Aufgabe 3.14. Es ergeben sich fixpunktfreie Permutationen.
Wir werden mit einer besseren Abzählmöglichkeit arbeiten. Auf diese Zahl kann man schneller kommen, indem man die Struktur von Permutationen besser versteht. Entscheidend dafür ist das Konzept eines Zyklus.
Es sei eine endliche Menge und eine Permutation auf . Man nennt einen Zykel der Ordnung , wenn es eine -elementige Teilmenge derart gibt, dass auf die Identität ist und die Elemente aus zyklisch vertauscht. Wenn ist, so schreibt man einfach
Dabei kann man statt jedes andere Element aus als Anfangsglied nehmen. Die Menge heißt auch der Wirkungsbereich des Zykels.
Es sei eine endliche Menge und eine Permutation auf . Es seien die Wirkungsbereiche der Zyklen von mit . Es sei und . Dann nennt man
die Zyklendarstellung von .
Wir erläutern dies kurz an einigen Permutationen auf einer vierelementigen Menge.
Bei der zuletzt angeführten Permutation wird auf und wiederum auf abgebildet, und ebenso wird mit vertauscht. Insgesamt kann man diese Abbildung als
darstellen. Man hat zwei Zykel der Länge zwei. In der darüber stehenden Permutation hat man die Zuordnung
Man spricht von einem Zyklus der Länge . In der darüber stehenden Permutation hat man die Zuordnung
Man hat einen Zyklus der Länge zwei und zwei Fixpunkte, ein Fixpunkt ist ein Zyklus der Länge eins. Die Zerlegung einer Permutation in die Zykel verschiedener Länge nennt man den Typ der Permutation. Es geht also darum, wie viele Zykel welcher Länge es gibt.
Im Falle gibt es nun lediglich zwei Typen, wie eine fixpunktfreie Permutation aussehen kann, nämlich den Viererzyklus und den doppelten Zweierzyklus. Beim ersten Typ kann man an jeder Stelle anfangen, die Reihenfolge der Elemente legt dann den Zyklus fest. Davon gibt es also Stück. Beim zweiten Typ geht es um die Einteilung der Menge in zwei Paare, danach ist alles festgelegt. Davon gibt es Stück. Jedenfalls ist die Wahrscheinlichkeit für eine fixpunktfreie Permutation bei vier Personen gleich .
Hier gibt es schon Permutationen, eine Auflistung erübrigt sich. Es gibt aber wieder nur zwei Typen von fixpunktfreien Permutationen, nämlich einerseits die -Zykel und andererseits diejenigen Permutationen, die aus einem Zweier-Zyklus und einem Dreier-Zyklus bestehen. Vom ersten Typ gibt es, mit dem gleichen Argument wie oben, Möglichkeiten. Vom zweiten Typ muss man die Anzahl der Möglichkeiten bestimmen, in einer fünfelementigen Menge eine zweielementige Teilmenge zu fixieren. In der fünfelementigen Menge gibt es genau
zweielementige Teilmengen. Wenn diese fixiert ist, muss man noch sagen, wie der Dreierzyklus auf dem Komplement aussehen soll. Dafür gibt es jeweils zwei Möglichkeiten. Insgesamt gibt es also unter den Permutationen
fixpunktfreie Permutationen. Die Wahrscheinlichkeit, eine erlaubte Wichtelzuordnung zu ziehen, ist somit
Für deutlich größere wird es auch mit der Zykelmethode schwierig, die genaue Anzahl der fixpunktfreien Permutationen zu bestimmen. Wir werden gleich eine bessere Methode kennenlernen. Wir fassen kurz die berechneten Wahrscheinlichkeiten zusammen.
In gerundeten Prozent ist dies
Diese Zahlen gehen hoch und runter. Wir möchten uns mit dem Problem beschäftigen, wie sich diese Zahlen verhalten, wenn groß und größer wird, gegen unendlich geht.
Wie verhalten sich die Wahrscheinlichkeiten, dass sich bei einer zufälligen Ziehung unter Personen eine wichtelkonforme Zuordnung ergibt, wenn die Personenanzahl gegen unendlich strebt.
Wie sieht es etwa für aus? „Streben“ die Wahrscheinlichkeiten einer bestimmten Zahl entgegen oder varieren sie in alle Richtungen? Wenn sie gegen eine bestimmte Zahl streben, gegen welche? Gegen , gegen , gegen irgendwas dazwischen?
Heuristisch ist es hier schwierig, einen Tipp abzugeben. Einerseits ist, wenn groß ist, die Wahrscheinlichkeit, dass eine Person sich selbst zieht, sehr klein. Andererseits darf aber gar keine Person sich selbst ziehen, und das sind wiederum viele Bedingungen, und viele kleine Wahrscheinlichkeiten können sich zu einer großen Zahl aufaddieren.
Wir beschreiben nun eine einfache Möglichkeit, für jedes die Anzahl der fixpunktfreien Permutationen anzugeben. Betrachten wir zuerst das Problem, dass bei einer Permutation eine bestimmte Person auf sich selbst abgebildet wird. Dies haben wir schon weiter oben für einzelne Zahlen bestimmt, es gibt Permutationen von dieser Art, da ja die eine Person auf sich selbst abgebildet wird, und es ansonsten keine weitere Bedingung gibt, es sich also einfach um die Gesamtzahl der Permutationen von Personen handelt. Falsch wäre es jetzt, diese Anzahl -mal aufzuaddieren, da wir dann eine Permutation mit mehreren Fixpunkten mehrfach zählen würden. Stattdessen müssen wir die Siebformel anwenden.
Die Anzahl der fixpunktfreien Permutationen auf einer Menge mit Elementen ist
Zu jedem sei die Menge aller Permutationen auf , die auf sich selbst abbilden. Somit ist die Menge aller Permutationen, die mindestens einen Fixpunkt haben. Um die Siebformel anwenden zu können, müssen wir zu die Durchschnitte verstehen. Bei dieser Menge handelt es sich um diejenigen Permutationen, für die alle Elemente aus Fixpunkte sind (und die auch noch weitere Fixpunkte außerhalb von haben können). Wenn die Anzahl von gleich ist, so gibt es solche Permutationen, da ja die Permutation auf die Identität sein muss und es außerhalb von keine Einschränkung gibt. Bei fixiertem wissen wir auch, wie viele Teilmengen mit Elementen zu berücksichtigen sind, nämlich . Mit diesen Zahlen ergibt sich nun mit Hilfe der Siebformel der Ausdruck
Somit ist die Anzahl der fixpunktfreien Permutationen gleich
Die Wahrscheinlichkeit, eine wichtelkonforme
(fixpunktfreie)
Permutation zu ziehen, ist somit gleich
Das Schöne an der jetzt gefundenen Formel ist, dass sich der nächste Wert (wenn man auf erhöht) durch Hinzunahme oder Abzug eines einfachen Bruches aus der zuvor berechneten Zahl ergibt. Vor allem aber erinnert die Formel an die Definition der Exponentialreihe, die die Exponentialfunktion beschreibt.
Dabei ist
die eulersche Zahl und
ist die inverse eulersche Zahl. Somit ist die oben ermittelte Formel für die Wahrscheinlichkeit, eine fixpuntfreie Permutation zu ziehen, gleich der Anfangssumme von . Insbesondere konvergiert diese Wahrscheinlichkeit gegen für gegen unendlich. Der numerische Wert ist
die oben zuletzt ausgerechneten Werte sind also schon ziemlich gut.
- Andere Auswahlverfahren
Beim üblichen Ziehen ist, wie wir gesehen haben, die Wahrscheinlichkeit, dass jemand sich selbst zieht und die Ziehung dann wiederholt werden muss, nicht zu vernachlässigen. Gibt es andere Auswahlverfahren? Es soll jede (fixpunktfreie) Zuordnung gleichwahrscheinlich sein und jede Person sollte außer der zu beschenkenden Person keinerlei weitere Information haben. Es sei zumindest . Wir besprechen zwei mögliche Ansätze.
Methode 1
Statt leerer Zettel nimmt man einseitig mit von bis durchnummerierte Zettel. Diese werden mit der Nummer nach unten hingelegt und jede Person zieht zufällig einen Zettel mit der Nummer, und zwar ohne den Zettel zurück zu legen. Nach diesem ersten Schritt besitzt also jede Person genau einen Zettel mit einer Nummer. Jede Person merkt sich ihre Nummer und schreibt auf ihrem Zettel den eigenen Namen auf der leeren Seite drauf. Die Zettel werden nun mit der Nummer nach oben wieder hingelegt, was die anderen wieder nicht sehen dürfen. Im letzten Schritt zieht nun jede Person ihre Nachfolgerzahl, wenn also eine Person die Nummer gezogen hat, muss sie jetzt den Zettel mit der Nummer rausgreifen (was im Fall als zu verstehen ist), den Zettel umdrehen und den Namen lesen. Die darauf stehende Person ist zu beschenken, der Zettel wird mit der Nummer nach oben wieder zurückgelegt. Bei diesem letzten Schritt müssen alle anderen Personen wegschauen, da es ja geheim sein soll, welche Nummer zu welcher Person gehört.
Diese Methode ist nicht ganz korrekt, da sie etwas Information über die Gesamtzuordnung mitliefert. Man weiß nämlich, dass die Person, der ich etwas schenken soll, definitiv nicht mein Schenker sein kann. Bei einer zufälligen Ziehung kann es aber sein, dass man selbst in einem Zweierzyklus landet.
Methode 2
Man macht für jede mögliche fixpunktfreie Permutation einen großen Umschlag (das sind also sehr viele Umschläge), der wiederum kleine Umschläge enthält. Auf jedem kleinen Umschlag steht außen ein Name und im Innern ist ein Zettel mit einem weiteren Namen. Jede Permutation kann man ja durch solche Umschläge kodieren, die kleinen Umschläge zusammen übernehmen also die Rolle der Wertetabelle. Die Gruppe muss dann einen großen Umschlag wählen, ihn öffnen und jede Person öffnet dann den kleinen Umschlag, auf dem ihr Name steht. Die im kleinen Umschlag innen benannte Person ist zu bewichteln.
Diese Methode ist mathematisch völlig korrekt, aber praktisch undurchführbar.