Логика и комбинаторика · 11 классКомбинаторика: формулы

Числа Каталана

Скобочные последовательности, пути под диагональю и триангуляции многоугольника — три задачи с одним и тем же ответом: числом Каталана.

Вариант № 14033

Числа Каталана · Вариант № 14033 · Обычный · Имя: ____________________

1
Сколько существует правильных скобочных последовательностей из 4 пар круглых скобок? (Правильная — когда скобки закрываются в правильном порядке, например «(())()».)
Ответ: 14
В правильной последовательности в любой начальной части открывающих скобок не меньше, чем закрывающих.
Перебор показывает $14$ . Формула Каталана: $\dfrac{1}{5}C_{8}^{4}=\dfrac{70}{5}=14$ .
2
По клетчатой сетке 3×3 идут из левого нижнего угла в правый верхний шагами вправо или вверх по линиям сетки, ни разу не поднимаясь выше пунктирной диагонали (касаться её можно). Сколько существует таких путей?
Ответ: 5
Всех путей $C_{6}^{3}=20$ , но часть из них заходит выше диагонали.
Те, что не заходят, считаются числами Каталана: $C_{3}=\dfrac{1}{4}C_{6}^{3}=5$ .
3
Сколько существует правильных скобочных последовательностей из 3 пар круглых скобок? (Правильная — когда скобки закрываются в правильном порядке, например «(())()».)
Ответ: 5
В правильной последовательности в любой начальной части открывающих скобок не меньше, чем закрывающих.
Перебор показывает $5$ . Формула Каталана: $\dfrac{1}{4}C_{6}^{3}=\dfrac{20}{4}=5$ .
4
Сколько существует правильных скобочных последовательностей из 6 пар круглых скобок? (Правильная — когда скобки закрываются в правильном порядке, например «(())()».)
Ответ: 132
В правильной последовательности в любой начальной части открывающих скобок не меньше, чем закрывающих.
Перебор показывает $132$ . Формула Каталана: $\dfrac{1}{7}C_{12}^{6}=\dfrac{924}{7}=132$ .
5
Выпуклый 5-угольник разрезают непересекающимися диагоналями на треугольники. Сколько существует разных способов такого разрезания?
Ответ: 5
Сторона между вершинами 1 и 5 входит ровно в один треугольник; его третья вершина — любая из остальных $3$ .
Каждый такой выбор разбивает многоугольник на две меньшие части, для которых задача решается так же. Складываем и умножаем — получаем числа Каталана.
Для $5$ -угольника: $C_{3}=5$ .

Коротко о теме

Число Каталана $C_n=\dfrac{1}{n+1}C_{2n}^n$ : $1,1,2,5,14,42,132,429,\dots$
$C_n$ — число правильных скобочных последовательностей из $n$ пар скобок.
$C_n$ — число путей из $(0,0)$ в $(n,n)$ шагами вправо и вверх, не поднимающихся выше диагонали $y=x$ .
$C_n$ — число способов разрезать выпуклый $(n+2)$ -угольник диагоналями на треугольники.

Уровни: Разминка · Обычный · Challenge. Все ответы вычислены программой из тех же чисел, что и условие.