Условие
Доказать, что n-е число Каталана (количество последовательностей длины 2n из n единиц и n минус
единиц, в любом начальном отрезке которых не меньше единиц, чем минус единиц) равно 
Подсказка
Число Каталана есть число ломаных, идущих из (0, 0) в (2n, 0) шагами (1, 1) и (1, –1), не опускающихся в нижнюю полуплоскость, то есть разность числа всех ломаных (которое равно 
) и числа ломаных, опускающихся в нижнюю полуплоскость. Последние можно описать также как ломаные, пересекающие прямую y = –1. Отразив их кусок справа от самой правой точки пересечения относительно указанной прямой, мы установим взаимно однозначное соответствие между ними и ломаными, идущими из (0, 0) в (2n, –2). Остаётся проверить, что 
Замечания
См. также решение задачи 60451.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
2 |
|
Название |
Порождение комбинаторных объектов |
|
параграф |
|
Номер |
7 |
|
Название |
Подсчёт количеств |
|
задача |
|
Номер |
2.7.3 |
