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

Давайте для начала в качестве леммы посмотрим на такую задачу, а потом решим исходную задачу.

Лемма. Пусть у нас есть учеников, и мы хотим расставить их в прямоугольник Но должно выполняться условие, что каждый ученик должен быть не выше того, кто стоит за ним и слева от него. Сколькими способами можно расставить людей, если все они разного роста?

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

______________________________________________________________________________________________________________________________________________________

Посмотрим теперь на таблицу из леммы. Покажем как из такой таблицы получить расстановки учеников Анатолия и Василия. Вычеркнув из нее числа от до получим первую “таблицу” — расстановку учеников Анатолия. Если вычеркнуть, наоборот, числа от до повернуть “таблицу” на и заменить каждое число на то получим вторую “таблицу” — расстановку учеников Виталия. Ясно, что такое отображение биективно, поскольку очевидно как построить к нему обратное. Количество расстановок, тем самым, равно