Олимпиадные задачи по теме «Числа Каталана» для 10 класса - сложность 3 с решениями
Числа Каталана
НазадВыведите формулу для чисел Каталана, воспользовавшись результатом задачи <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 точек. Сколькими способами можно провести пять отрезков, не имеющих общих точек, с концами в данных точках?