Какие задачи в комбинаторике решаются с помощью чисел Каталана?

Числа Каталана встречаются в большом количестве задач комбинаторики. www.e-maxx-ru.1gb.ru Некоторые из них:

• Количество корректных скобочных последовательностей, состоящих из открывающих и закрывающих скобок. www.e-maxx-ru.1gb.ru ru.wikipedia.org
• Количество корневых бинарных деревьев с n+1 листьями (вершины не пронумерованы). www.e-maxx-ru.1gb.ru
• Количество способов полностью разделить скобками множитель. www.e-maxx-ru.1gb.ru
• Количество триангуляций выпуклого n+2-угольника (разбиений многоугольника непересекающимися диагоналями на треугольники). www.e-maxx-ru.1gb.ru ru.wikipedia.org
• Количество способов соединить 2n точек на окружности непересекающимися хордами. www.e-maxx-ru.1gb.ru ru.wikipedia.org
• Количество неизоморфных полных бинарных деревьев с внутренними вершинами (имеющими хотя бы одного сына). www.e-maxx-ru.1gb.ru
• Количество монотонных путей из точки (0,0) в точку (n,n) в квадратной решётке размером n × n, не поднимающихся над главной диагональю. www.e-maxx-ru.1gb.ru
• Количество перестановок длины, которые можно отсортировать стеком. www.e-maxx-ru.1gb.ru
• Количество непрерывных разбиений множества из элементов (т. е. разбиений на непрерывные блоки). www.e-maxx-ru.1gb.ru
• Количество способов покрыть лесенку с помощью прямоугольников (имеется в виду фигура, состоящая из столбцов, i-ый из которых имеет высоту). www.e-maxx-ru.1gb.ru