Олимпиадные задачи по теме «Числа Каталана» для 11 класса - сложность 2 с решениями
Числа Каталана
НазадДокажите, что числа Каталана удовлетворяют рекуррентному соотношению <i>C<sub>n</sub></i> = <i>C</i><sub>0</sub><i>C</i><sub><i>n</i>–1</sub> + <i>C</i><sub>1</sub><i>C</i><sub><i>n</i>–2</sub> + ... + <i>C</i><sub><i>n</i>–1</sub><i>C</i><sub>0</sub>.
Определение чисел Каталана <i>C<sub>n</sub></i> смотри в <a href="https://problems.ru/thes.php?letter=23#chisla_catalana">справочнике</a>.
Билеты стоят 50 центов, и 2<i>n</i> покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные – по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу?
Рассмотрим шахматную доску <i>n×n</i>. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько у ладьи существует таких маршрутов?