I numeri di Catalan contano esattamente quante permutazioni di 1, 2, …, n possono essere ordinate utilizzando un singolo stack. Immagina una macchina che legge i numeri da 1 a n in ordine. Ad ogni passo, puoi o spingere il numero successivo su uno stack, o estrarre dallo stack per l'output. Alcuni ordinamenti di output sono realizzabili, altri no. Il conteggio? Esattamente Cₙ, il n-esimo numero di Catalan.