Задача № 177913
На окружности расположены 20 точек. Эти 20 точек попарно соединяются 10 хордами, не имеющими общих концов и непересекающихся. Сколькими способами это можно сделать?
Олимпиадные задачи по теме «Числа Каталана» для 1-10 класса
Найдите задачу для урока, кружка или самостоятельной работы.
Задача № 161520
Выведите формулу для чисел Каталана, воспользовавшись результатом задачи 161519 и равенством где – обобщенные биномиальные коэффициенты. Определение чисел Каталана можно найти в справочнике.
Задача № 161519
Пусть – производящая функция последовательности чисел Каталана. Докажите, что она удовлетворяет равенству C(x) = xC²(x) + 1, и получите явный вид функцииC(x). Определение чисел Каталана можно найти всправочнике.
Задача № 160557
При помощи формулы Лежандра (см. задачу 160553) докажите, что число целое.
Задача № 160452
Докажите, что числа Каталана удовлетворяют рекуррентному соотношению Cn = C0Cn–1 + C1Cn–2 + ... + Cn–1C0. Определение чисел Каталана Cn смотри в справочнике.
Задача № 160451
а) Пусть {a1, a2,..., an} – последовательность целых чисел, сумма которых равна 1. Докажите, что ровно у одного из ее циклических сдвигов {a1, a2, ..., an}, {a2, ..., an, a1}, ..., {an, a1, ..., an–1} все частичные суммы (от начала до произвольного элемента) положительны. б) Выведите отсюда равенства: где (4n – 2)!!!! = 2·6·10·...(4n – 2) – произведение, в котором участвует каждое четвёртое число. Определение чисел Каталана Cn смотри в справочнике.
Задача № 160450
Билеты стоят 50 центов, и 2n покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные – по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу?
Задача № 160449
Рассмотрим шахматную доску n×n. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько у ладьи существует таких маршрутов?
Задача № 160448
Сколько существует способов разрезать выпуклый (n+2)-угольник диагоналями на треугольники?
Задача № 160447
Сколько последовательностей {a1, a2, ..., a2n}, состоящих из единиц и минус единиц, обладают тем свойством, что a1 + a2 + ... + a2n = 0, а все частичные суммы a1, a1 + a2, ..., a1 + a2 + ... + a2n неотрицательны?
Задача № 132082
На окружности даны 10 точек. Сколькими способами можно провести пять отрезков, не имеющих общих точек, с концами в данных точках?