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:

Trajektorien

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:

Baum

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.  Σn0 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  Σn0 P(n)  ausreicht, wenn wir  Σn0 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:

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:

Binomialreihe fuer s=1/2

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  Σn0 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 =  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


Manfred Börgens   |    zur Leitseite