Auf einem 4 × 4-Gitter zählen die Routen von der linken unteren zur rechten oberen Ecke, die nur nach oben und rechts gehen, 8!/(4!·4!) = 70 – der Rechner zeigt das im zweiten Link. Die meisten fügen die Regel „nie über die Diagonale gehen“ hinzu, und dann ist die Zahl 8!/(4!·5!) = 14. Die beiden Formeln unterscheiden sich um einen Faktor n + 1 im Nenner, das ist die ganze Catalan-Korrektur.
Die 56 unerlaubten Wege sind nicht verstreut: Nach dem Spiegelungsargument paart das Kreuzen der Diagonalen sie eins zu eins mit den Routen zu einem verschobenen Endpunkt, und die zählen 8!/(3!·5!) = 56. Also 70 − 56 = 14, und die beiden Bildschirme stimmen überein. Dieselbe Folge 1, 2, 5, 14, 42 zählt die Möglichkeiten, Klammern in eine Kette von Faktoren einzusetzen, die Triangulierungen eines konvexen Polygons und die erlaubten Klammerausdrücke – der dritte Link ist C₅ = 10!/(5!·6!) = 42, die nächste, die Zahl der Triangulierungen eines Siebenecks.
Antwort
14
So lesen Sie sie
C₄ als 8!/(4!·5!) auf dem Rechner. Der zweite Link ist die uneingeschränkte Zählung 8!/(4!·4!) = 70, und der dritte ist die nächste Catalan-Zahl, 42.
Quelle
The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838
Im Rechner durchrechnen
Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.