Задача № 160452
Докажите, что числа Каталана удовлетворяют рекуррентному соотношению Cn = C0Cn–1 + C1Cn–2 + ... + Cn–1C0. Определение чисел Каталана Cn смотри в справочнике.
Олимпиадные задачи по теме «Числа Каталана» для 11 класса - сложность 2 с решениями
Найдите задачу для урока, кружка или самостоятельной работы.
Задача № 160450
Билеты стоят 50 центов, и 2n покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные – по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу?
Задача № 160449
Рассмотрим шахматную доску n×n. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько у ладьи существует таких маршрутов?