Vier Schritte hoch und vier quer, ohne die Diagonale zu kreuzen: 14 der 70 Wege

Der zentrale Binomialkoeffizient zählt alle Routen; die Catalan-Formel zählt die erlaubten.

Statistik und Daten · Niveau: Klassisches Ergebnis · Aktualisiert am 2026-11-10

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.

Dies ist eine unabhängige Tool-Website eines Drittanbieters. Sie ist weder mit Casio, Texas Instruments oder deren Vertriebspartnern verbunden noch von ihnen gesponsert oder autorisiert. Modell- und Produktnamen sind Marken der jeweiligen Inhaber und erscheinen hier nur zur Identifizierung der Geräte.

Die Tastenfolgen in diesen Handbüchern wurden aus den eigenen Layoutdaten dieser Website erstellt — denselben Daten, die der Online-Rechner darstellt — sowie aus öffentlich verfügbaren Produktinformationen. Spezifikationen und regionale Konfigurationen werden am physischen Gerät und anhand der neuesten Unterlagen des Herstellers überprüft.