Олимпиадные задачи по теме «Числа Каталана» - сложность 3 с решениями
Числа Каталана
НазадДоказать, что <i>n</i>-е <i>число Каталана</i> (количество последовательностей длины 2<i>n</i> из <i>n</i> единиц и <i>n</i> минус единиц, в любом начальном отрезке которых не меньше единиц, чем минус единиц) равно <img align="absmiddle" src="/storage/problem-media/98842/problem_98842_img_2.gif">
На окружности расположены 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>.
При помощи <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>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>} все частичные суммы (от начала до произвольного элемента) положит...
Сколько существует способов разрезать выпуклый (<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 точек. Сколькими способами можно провести пять отрезков, не имеющих общих точек, с концами в данных точках?