Manfred Börgens Mathematische Probleme # 88 |
Liste aller Probleme mit Lösungen voriges Problem nächstes Problem |
zur Leitseite |
Vom Theaterkassenproblem über die Catalan-Zahlen zur Familienplanung
Wir stellen ein (natürlich hypothetisches) Problem der Familienplanung vor: In einem Land strebt jede Mutter an, solange Kinder zu bekommen, bis sie genau einen Jungen mehr hat als Mädchen. Es soll uns hier nicht kümmern, dass das kaum praktikabel erscheint. Aber aus dieser Strategie entstehen eine Reihe von Fragen, u.a. diese: Wie groß ist die Wahrscheinlichkeit, dass es einer Mutter nie gelingt, ihr Ziel zu erreichen, selbst wenn sie beliebig viele Kinder bekommen könnte? Wieviele Kinder hat eine Mutter im Durchschnitt? Wird es in diesem Land auf Dauer mehr Jungen als Mädchen geben?
Um zur Lösung zu gelangen, machen wir einen Umweg und fangen bei einem gut bekannten anderen Problem an, dem Theaterkassenproblem.
Theaterkassenproblem
Eine Eintrittskarte für eine Theatervorstellung kostet 50 Euro. Es hat sich an der Kasse eine Schlange von 2n Besuchern gebildet, von denen n einen 50-Euro-Schein haben und die anderen n einen 100-Euro-Schein. Bei Beginn des Kartenverkaufs hat der Kassierer kein Wechselgeld. Mit welcher Wahrscheinlichkeit qn erlaubt die (zufällige) Reihenfolge der Besucher in der Schlange eine lückenlose Abfertigung an der Kasse? (Der Kassierer soll also jedem Besucher, der einen 100-Euro-Schein hinlegt, sofort einen bereits eingenommenen 50-Euro-Schein zurückgeben können.) |
Die Lösung des Theaterkassenproblems kann leicht durch Probieren gefunden werden. Zunächst soll eine Notation vereinbart werden, die die Warteschlange beschreibt. Ein "+" soll für einen 50-Euro-Schein und ein "-" für einen 100-Euro-Schein stehen. Für n = 6 würde diese Warteschlange problemlos abgefertigt:
+ - + + - + - - + + - -
Die folgende Warteschlange könnte nicht der Reihe nach bedient werden:
+ + + - - - - + + - + -
Wir betrachten also endliche Folgen aus "+" und "-" der Länge 2n mit gleich vielen "+" und "-" . Solche Folgen wollen wir n-ausgeglichen nennen. Aus kombinatorischer Sicht handelt es sich um Permutationen mit Wiederholung. Bei der ersten Warteschlange ist nach jedem Abschnitt der Folge die Anzahl der "+" mindestens so groß wie die Anzahl der "-" . Solche Folgen sollen +führend genannt werden. Die zweite Folge ist nicht +führend.
Aufgabe 1
Berechnen Sie die Anzahl An der n-ausgeglichenen Folgen.
Aufgabe 2
Bestimmen Sie die Anzahl Cn der +führenden Folgen unter den n-ausgeglichenen Folgen für n ≤ 4 .
Aus Cn/An ergibt sich eine Vermutung für eine allgemeine Formel der Cn .
Das geht ziemlich schnell durch Ausprobieren, wenn man beachtet, dass vorne immer ein "+" und hinten immer ein "-" stehen muss. Für n = 4 bleiben dann nur noch 6 freie Plätze, die für die +führenden Folgen gefüllt werden müssen.
Die Cn bilden die Folge der Catalan-Zahlen, die eine wichtige Rolle in der diskreten Mathematik spielen. Die Vermutung aus Aufgabe 2 wird in vielen Quellen mit Hilfe einer erzeugenden Funktion bewiesen, aber es gibt auch einen eleganten elementaren Beweis. Dazu stellen wir die Folge der n-ausgeglichenen Folgen graphisch dar. Wir zeichnen einen Pfad in 2n Schritten von (0,0) nach (2n,0) ; einem "+" entspricht eine Diagonale von (a,b) nach (a+1,b+1) und einem "-" eine Diagonale von (a,b) nach (a+1,b-1) . Die beiden Folgen unterhalb des Theaterkassenproblems hätten dann die folgenden Darstellungen:
Die +führenden Folgen werden durch Pfade dargestellt, die nirgends durch die untere Halbebene verlaufen.
Um die Formel für die Catalan-Zahlen zu beweisen, berechnet man zuerst die Anzahl der Folgen, die nicht +führend sind, und subtrahiert dann diese Anzahl von An . Dazu ein Tipp: Die nicht +führenden Folgen der Länge 2n haben die gleiche Anzahl wie alle Folgen der Länge 2n mit n-1 "+" und n+1 "-" . Um sich dies zu veranschaulichen, ist die graphische Darstellung hilfreich.
Aufgabe 3
Bestimmen Sie Cn für alle n ∈ N (mit Beweis).
Lösen Sie damit das Theaterkassenproblem.
Bevor wir endlich zum eigentlichen Problem der Familienplanung kommen, soll noch eine Anwendung der Catalan-Zahlen in der Graphentheorie erwähnt werden, die planaren Bäume. Hier ist ein Bild eines planaren Baums:
Das Bild zeigt einen hierarchischen (in Ebenen angeordneten) Graphen, der auf der obersten Ebene nur einen Knoten hat (die Wurzel). Alle Knoten können zur darunter liegenden Ebene endlich viele Verzweigungen haben, aber alle Knoten außer der Wurzel haben genau eine Kante zur nächsthöheren Ebene. Es gibt keine Kanten innerhalb einer Ebene. Für die Bestimmung der Anzahl planarer Bäume ist die Orientierung links-rechts von Bedeutung, d.h. in dem abgebildeten Baum würde durch die Vertauschung der beiden Knoten auf der dritten Ebene (mitsamt ihren Unterbäumen) ein anderer planarer Baum entstehen. Hat ein solcher Baum n+1 Knoten, so lässt er sich durch eine +führende n-ausgeglichene Folge beschreiben. (Tipp: Man durchlaufe den Baum von der Wurzel durch alle Knoten bis zurück zur Wurzel und unterscheide n Abwärtsschritte und n Aufwärtsschritte.)
Aufgabe 4
Zeigen Sie: Es gibt Cn planare Bäume mit n+1 Knoten.
Ausgehend von der Anwendung der Catalan-Zahlen bei planaren Bäumen wird nun zusätzlich C0 = 1 definiert. Dies harmoniert auch mit der in Aufgabe 3 hergeleiteten Formel.
Nun zur Familienplanung, wie sie zu Beginn beschrieben wurde. Offenbar haben alle Mütter, die das Ziel erreicht haben, eine ungerade Anzahl 2n+1 von Kindern, also n+1 Jungen und n Mädchen, n ∈ N0. Die Folge der Kinder notieren wir mit "+" für die Mädchen und mit "-" für die Jungen. Hier sind die beiden möglichen Kinderfolgen bei 5 Kindern (n = 2) :
+ + - - -
+ - + - -
Der Zusammenhang mit dem Theaterkassenproblem und den Catalan-Zahlen ist leicht erkennbar. Wir wollen unterstellen, dass Mädchen und Jungen jeweils mit Wahrscheinlichkeit 1/2 geboren werden.
Aufgabe 5
Wie groß ist die Wahrscheinlichkeit pn , dass eine Mutter genau 2n+1 Kinder bekommt?
Es soll nun gezeigt werden, dass P(n)= pn eine diskrete Wahrscheinlichkeitsverteilung auf N0 ist, d.h. Σn≥0 P(n) = 1 . Das hat eine wichtige Konsequenz: Das Ereignis "1 Junge mehr" stellt sich irgendwann sicher ein. Anders ausgedrückt: Die Wahrscheinlichkeit, dass eine Mutter trotz beliebig vieler Versuche auf Dauer mindestens so viele Mädchen wie Jungen unter ihren Kindern hat, ist 0 .
Die Lösung von Aufgabe 5 zeigt uns, dass es für die Berechnung von Σn≥0 P(n) ausreicht, wenn wir Σn≥0 Cn·xn als geschlossene Funktion f(x) ausdrücken können. Die Summe ist dann die Potenzreihe zu f(x) und heißt erzeugende Funktion der Cn . Dies ist der schwierigste Teil auf dieser Problemseite, aber es wird Schritt für Schritt durch den Beweis geführt.
f(x) hat also eine Potenzreihe, deren Koeffizienten Cn bekannt sind. Für sehr viele Funktionen finden sich die zugehörigen Potenzreihen in Tafelwerken oder im Internet. In der Hoffnung, dass man unter den gängigen Reihen fündig wird, stößt man schnell auf die Binomialreihe:
a kann später noch passend gewählt werden. Für s muss man ein wenig probieren, damit die Reihe zu den Catalan-Zahlen passt. s = 1/2 erweist sich als guter Kandidat:
Die letzte Reihe führt mit Indexverschiebung und geeigneter Wahl von a auf die gesuchte Potenzreihe, d.h. auf die erzeugende Funktion der Cn . Behalten Sie dabei auch den Konvergenzbereich der Potenzreihe im Auge.
Aufgabe 6
Beweisen Sie Σn≥0 P(n) = 1 mit Hilfe der erzeugenden Funktion für Cn .
Aufgabe 7
Die P(n) verhalten sich für n > 0 näherungsweise wie d n = D· nr . Bestimmen Sie r und D mit Hilfe der Stirling'schen Formel.
Aufgabe 8
Wird es in diesem Land auf Dauer mehr Jungen als Mädchen geben?
Aufgabe 9
Welcher Anteil der Mütter ist spätestens nach dem 5., 11. bzw. 21. Kind am Ziel angelangt?
Aufgabe 10
Berechnen Sie den Erwartungswert für die Anzahl der Kinder pro Mutter.
Auch hier hilft die Stirling'sche Formel.
Lösung
Publiziert 2014-09-16 Stand 2014-01-19
voriges Problem | Liste aller Probleme mit Lösungen | nächstes Problem