Die Catalan-Zahlen zählen genau, wie viele Permutationen von 1, 2, …, n mit einem einzigen Stapel sortiert werden können. Stellen Sie sich eine Maschine vor, die die Zahlen von 1 bis n der Reihe nach liest. Bei jedem Schritt können Sie entweder die nächste Zahl auf einen Stapel legen oder eine Zahl vom Stapel in die Ausgabe nehmen. Einige Ausgabereihenfolgen sind erreichbar, andere nicht. Die Anzahl? Genau Cₙ, die n-te Catalan-Zahl.