ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98842
Темы:    [ Нерекурсивная генерация объектов ]
[ Числа Каталана ]
Сложность: 4
Классы:
В корзину
Прислать комментарий

Условие

Доказать, что 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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .