Числа Каталана точно подсчитывают, сколько перестановок 1, 2, …, n можно отсортировать с помощью одного стека. Представьте себе машину, которая считывает числа от 1 до n в порядке. На каждом шаге вы либо добавляете следующее число в стек, либо извлекаете из стека для вывода. Некоторые порядки вывода достижимы, некоторые — нет. Счет? Точно Cₙ, n-е число Каталана.