Wie oft muss man ziehen, bis man den Inhalt der Urne kennt?
Die Überschrift muss natürlich präzisiert werden. Hier geht es um eine Urne mit endlich vielen paarweise unterscheidbaren Kugeln, die mit Zurücklegen gezogen werden – und zwar solange, bis jede Kugel mindestens einmal gezogen wurde.
Stellen Sie sich z.B. vor, dass Sie vor dem Ziehen darüber informiert wurden, dass die Urne \(~m~\) Kugeln in \(~m~\) paarweise verschiedenen Farben enthält. Sie möchten wissen, um welche Farben es sich handelt und ziehen solange, bis Sie alle Farben kennen.
|
 |
|
Für \(~m=6~\) bietet sich die folgende Umformulierung an: Wie oft muss man würfeln, bis jede Zahl mindestens einmal erschienen ist?
Man kann sich am Würfel-Beispiel orientieren und der Einfachheit halber den Farben die Zahlen \(~1,~...,~m~\) zuordnen, z.B. alphabetisch. Notiert man, welche Zahlen gezogen werden, erhält man eine Folge, in der alle Zahlen zwischen \(~1~\) und \(~m~\) vorkommen, davon möglicherweise manche mehrfach, aber die letzte nur einmal.
Die Frage aus der Überschrift zerfällt in zwei Probleme:
- Wie groß ist die Wahrscheinlichkeit, dass man genau \(~n~\) Ziehungen benötigt, bis man alle Farben gesehen hat?
- Wieviele Ziehungen benötigt man im Mittel?
Falls Sie einen Tipp für die erste Frage haben möchten, markieren Sie den Rest dieses Abschnitts: Offenbar handelt es sich um surjektive Abbildungen f: {1, ..., n} → {1, ..., m}, deren Anzahl man nachschauen kann. Hier gibt es allerdings die Einschränkung, dass f(n) eindeutig sein muss.
Falls Sie einen Tipp für die zweite Frage haben möchten, folgen Sie dem Link zu diesem → Lemma.
Die Lösung erscheint Anfang Juli.
Publiziert 2026-05-31 Stand 2025-03-06
voriges Problem | Liste aller Probleme mit Lösungen
Manfred Börgens |
zur Leitseite