Олимпиадные задачи по теме «Числа Каталана» для 7-10 класса
Числа Каталана
НазадНа окружности расположены 20 точек. Эти 20 точек попарно соединяются 10 хордами, не имеющими общих концов и непересекающихся.
Сколькими способами это можно сделать?
Выведите формулу для чисел Каталана, воспользовавшись результатом задачи <a href="https://mirolimp.ru/tasks/161519">161519</a> и равенством <img align="absmiddle" src="/storage/problem-media/61520/problem_61520_img_2.gif"> где
<img align="absmiddle" src="/storage/problem-media/61520/problem_61520_img_3.gif"> – обобщенные биномиальные коэффициенты.
Определение чисел Каталана можно найти в <a href="https://problems.ru/thes.php?%20letter=23#chisla_catalana">справочнике</a>.
Пусть <img align="absmiddle" src="/storage/problem-media/61519/problem_61519_img_2.gif"> – производящая функция последовательности <i>чисел Каталана</i>. Докажите, что она удовлетворяет равенству <div align="CENTER"><i>C</i>(<i>x</i>) = <i>xC</i>²(<i>x</i>) + 1, </div>и получите явный вид функции<i>C</i>(<i>x</i>). Определение чисел Каталана можно найти в<a href="https://problems.ru/thes.php?letter=23#chisla_catalana">справочнике</a>.
При помощи <i>формулы Лежандра</i> (см. задачу <a href="https://mirolimp.ru/tasks/160553">160553</a>) докажите, что число <img align="absmiddle" src="/storage/problem-media/60557/problem_60557_img_2.gif"> целое.
Докажите, что числа Каталана удовлетворяют рекуррентному соотношению <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>.
а) Пусть {<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>,..., <i>a<sub>n</sub></i>} – последовательность целых чисел, сумма которых равна 1. Докажите, что ровно у одного из ее циклических сдвигов
{<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>}, {<i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>, <i>a</i><sub>1</sub>}, ..., {<i>a<sub>n</sub></i>, <i>a</i><sub>1</sub>, ..., <i>a</i><sub><i>n</i>–1</sub>} все частичные суммы (от начала до произвольного элемента) положит...
Билеты стоят 50 центов, и 2<i>n</i> покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные – по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу?
Рассмотрим шахматную доску <i>n×n</i>. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько у ладьи существует таких маршрутов?
Сколько существует способов разрезать выпуклый (<i>n</i>+2)-угольник диагоналями на треугольники?
Сколько последовательностей {<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a</i><sub>2<i>n</i></sub>}, состоящих из единиц и минус единиц, обладают тем свойством, что <i>a</i><sub>1</sub> + <i>a</i><sub>2</sub> + ... + <i>a</i><sub>2<i>n</i></sub> = 0, а все частичные суммы <i>a</i><sub>1</sub>, <i>a</i><sub>1</sub> + <i>a</i><sub>2</sub>, ..., <i>a</i><sub>1</sub> + <i>a</i><sub>2</sub> + ... + <i>a</i><sub>2<i>n</i></sub> неотрицательны?
На окружности даны 10 точек. Сколькими способами можно провести пять отрезков, не имеющих общих точек, с концами в данных точках?