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

Скажем, что самый высокий школьник имеет номер следующий по росту — и так далее. Мы хотим расставить числа от до в таблицу так, чтобы в каждой ячейке число было больше, чем в ячейке выше и в ячейке левее неё. Давайте, вновь, рассмотрим пути Дика (пути по линиям сетки, не поднимающиеся выше ) из в Построим отображение, сопоставляющее пути Дика расстановку чисел в таблице: если в пути мы идём направо, то запишем номер хода в первую строку, а если вверх, то в нижнюю строку. Условие того, что каждое число больше, чем сосед слева, выполнено по построению, а условие того, что каждое число во второй строке больше, чем сосед сверху, равносильно тому, что в любой момент времени число шагов вверх не превосходит число шагов направо. Поэтому отображение возвращает правильную расстановку чисел в таблице, а обратное отображение возвращает путь Дика. Поскольку между множествами путей Дика и расстановок чисел в таблице существует биекция, их мощности совпадают, и ответом является