Числа Каталана

Переведем задачу на язык последовательностей: необходимо найти число последовательностей натуральных чисел где В одной из предыдущих задач мы поняли, что числа Каталана можно представить путями из в по линиям сетки, и не переступающими за Ясно, что если имеется подобный путь, и для каждого значения по от до мы выделим наибольшее значение по лежащее на пути до момента включительно, и прибавим к нему единицу, то мы получим последовательность из нашего условия. Разумеется, она будет неубывающей, и ее -ый элемент не будет превосходить И наоборот, по последовательности можно построить путь по решетке из в не пересекающий Его первый шаг всегда направо, а дальше для от 2 до сделаем последовательность из шага наверх и одного шага вправо. Из свойства последовательности, на своем пути мы ни разу не пересекли Ясно, что в конце мы находимся в точке с координатой по оси ниже прямой  – остается сделать необходимое число шагов, чтобы попасть в точку

Нетрудно видеть, что построенные отображения являются взаимно обратными. Значит, у нас есть биекция между двумя множествами объектов, откуда их размеры равны. Поэтому искомое количество способов из условия задачи равно