Lösungsskizze zum erweiterten Catalan-Problem

Aufgabenstellung: Eine Eintrittskarte für die Abendvorstellung kostet 20€. Um die Wartezeiten an der Kasse zu reduzieren, wurden alle Ticket-Interessenten gebeten, möglichst 2 x 10€-Scheine, notfalls einen 50€-Schein parat zu halten. In der Warteschlange befinden sich insgesamt Z Personen mit zwei 10€-Scheinen und F Personen bezahlen mit einem Fünfziger. Zu Beginn des Kartenverkaufs befanden sich 60€ ( in Zehnern ) in der Wechselkasse! Berechne die Wahrscheinlichkeit, dass niemand auf sein Wechselgeld warten muss, für Z = 9 und F = 6.

In nebenstehendem Gitternetz ist die Anzahl der zulässigen 'Pfade' zu den einzelnen Gitternetz-Schnittpunkten in Abhängigkeit von Z und F eingetragen. Diese Zahlen wurden mit Hilfe der Rekurrenz   M( Z , F ) = M( Z - 1, F ) + M( Z , F - 1 ) ermittelt! Die rote Begrenzungslinie des zulässigen Bereiches ist von dem anfänglich vorhandenen Wechselgeld abhängig! Bei größeren Warteschlangen empfiehlt sich die Verwendung eines Computerprogramms zur Ermittlung der Anzahl zulässiger 'Pfade'. Der Aufgabenstellung entsprechend entnimmt man der Matrix die Anzahl der zulässigen Warteschlangen zu anz = M[9][6] = 3581 Die Anzahl der möglichen - aber nicht unbedingt zugelassenen - Warteschlangen N ergibt sich mit Hilfe der Formel für Permutationen mit Wiederholungen zu: N = ( F + Z )! / ( F! * Z! ) = 5005. Für die gesuchte Wahrscheinlichkeit ergibt sich somit:    P = anz / N = 0,715484515.