Сколько правильных скобочных слов длины 2n
Число Каталана C_n считает, сколькими способами написать n пар скобок, чтобы они правильно вкладывались: префикс никогда не имеет больше закрывающих, в конце баланс нулевой. Раздел: комбинаторика.
Контроль: C_0 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42.
n целое 0…20. Родитель математика.
C_n = C(2n, n) / (n + 1)
C_n = C(2n, n) / (n + 1)
Искомое — C. Сначала биномиальный коэффициент C(2n, n), затем деление на n+1. Результат всегда целое.
Не сочетание C(n,k)
Не подмножества из n по k: там два параметра. Не значение (a+b)ⁿ. Не n! и не разбиения множества.
Как пользоваться
Одно поле — индекс n. Для скобок длины 6 берите n = 3 → 5 слов. Не кладите 6 как «длину строки» без деления пополам.
Примеры
1. Пусто. C_0 = 1.
2. Две пары. C_2 = 2: ()() и (()).
3. Три пары. C_3 = 5.
4. Четыре. C_4 = 14.
5. Пять. C_5 = 42.
Ещё задачи
Путь по сетке n×n, не выше диагонали: тоже C_n. Из (0,0) в (n,n) шагами восток и север, не заходя выше y = x.
Триангуляции выпуклого (n+2)-угольника: C_n. Для шестиугольника n = 4 → 14.
Связь с C(8,4): 70, делите на 5 → 14. Не оставляйте 70.
Рекурсия C_0 = 1, C_{n+1} = Σ C_i C_{n−i}. Страница явную формулу, сумму свёртки не просит.
Не кладите k вторым параметром: его нет.
Бинарные деревья с n+1 листьями: снова C_n в одной из нормализаций. Уточняйте учебник, индекс иногда сдвинут.
Строка бинома n = 6 содержит C(6,3) = 20, это не C_3 = 5.
Очередь к кассе с купюрами: n людей с 100 и n с 50, сдача всегда есть — C_n, если купюра кассы как скобка.
Одна размерность: число объектов Каталана, не длина скобки 2n в ответе.
Два независимых слова — произведение двух C, не C_{n+m}.
Пути Дика
Чертёж: ломаная вверх-вниз, не уходит ниже нуля, конец на нуле. Число таких длины 2n есть C_n.
Памятка: делить C(2n,n) на n+1, не путать с C(n,k).
Хаб комбинаторики рядом с сочетаниями, потому что в формуле сидит C(2n,n).
Итог: индекс n, целое, пустой 1.
Деревья и триангуляции
Корневые бинарные деревья, плоские деревья, расстановки множителей в произведении n+1 сомножителей (a₁·a₂·…): семейство Каталана. Не подставляйте число вершин вместо n без сверки определения.
Выпуклый пятиугольник: n = 3 стороны «лишние» к треугольнику? (n+2) = 5 ⇒ n = 3 → 5 триангуляций. Не C(5,2).
Родитель математика. Сосед по коэффициенту: C.
Итог журнала: C_n = C(2n,n)/(n+1), скобки, не подмножество k из n.
Контроль: 1; 2; 5; 14; 42.
Пример: C_6 = C(12,6)/7 = 924/7 = 132.
Не подставляйте 2n в поле n.
Рабочий пример: C_8 = 1430. Скобки длины 16.
Связь с факториалами: C(2n,n) = (2n)! / (n!)^2, затем / (n+1) = (2n)! / (n! (n+1)!).
Итог для отчёта: индекс, сочетание удвоенного, деление на n+1.
Финальный якорь: C_4 = 14. C_0 = 1.
Добор: не называйте C_n «сочетаниями из 2n по n» без деления.
Ещё якорь: C_1 = 1. Одна пара скобок.
Журнал: стек и вход 1…n, выход — перестановки, избегающие 231, их C_n. Не все n!.
Не путайте с P.
Финальный блок: Каталан, скобки, пути, n ≤ 20, один индекс.
Ещё контроль: C_7 = 429. C_9 = 4862.
Почему делят на n+1? Циклическая лемма / балет: среди 2n+1 позиций ровно одна делает слово Дика. Эквивалентно C(2n,n)−C(2n,n−1).
Итог абзаца: баланс скобок, неотрицательный префикс.
Связь с биномом: коэффициент середины чётной строки, урезанный.
Две независимые расстановки скобок — произведение.
Финальный добор: C_n Каталана, не C(n,k), не n!, не Стирлинг.
Отчёт: «четырнадцать» без индекса 4 не отличить от C_n других.
Стык с C(8,4): 70 — полуфабрикат.
Не кладите k = n.
Якорь: 1; 2; 5; 14; 42. Длину 2n в поле n не кладите.
Приложение: монеты орёл-решка, никогда не уходим в минус, n орлов и n решек — C_n.
Одинаковые скобки другого алфавита [] {} смешивать нельзя без модели много типов — тогда числа Фусса-Каталана, не эта страница.
Повторный расчёт после смены индекса: n = 5 не «пять скобок», а пять пар.
Рекурсия Каталана C_0 = 1 и C_{n+1} = Σ C_i C_{n−i} по i от 0 до n даёт те же целые: C_3 = C_0 C_2 + C_1 C_1 + C_2 C_0 = 2 + 1 + 2 = 5. Страница считает через бином, сумму свёртки не вводит как поле.
Путь Дика на решётке: шаг вверх и вниз, не ниже нуля, финиш на нуле после 2n шагов. Число таких путей — C_n, не C(2n,n) свободных путей без барьера.
Сосед S(n,k) режет множество, Каталан считает плоские деревья и скобки: разные объекты, разные таблицы.
Типичные ошибки
- Оставить C(2n,n) без деления.
- Путать с C(n,k).
- Класть длину строки 2n в n.
- Сдвинуть индекс на единицу по учебнику деревьев.
- Дробный n.
Соседи: сочетания, бином Ньютона, факториал, размещения, Стирлинг.
Итог добора: C_n = C(2n,n)/(n+1), правильные скобки, один индекс 0…20.
Частые вопросы
- Чему равно четвёртое число Каталана?
- C_4 = C(8,4)/5 = 70/5 = 14. Индекс с нуля: C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14.
- Это обычные сочетания из n по k?
- C(n,k) — другое. Здесь только диагональ C(2n,n), ещё делят на n+1.
- Где бином Ньютона?
- (a+b)ⁿ суммирует все коэффициенты. Каталан берёт один и делит.
- C_0 почему 1?
- Пустая скобочная строка одна. C(0,0)/1 = 1.
- n больше 20?
- Страница не считает. Учебный ряд до 20.
- Где хаб?
- Комбинаторика.
Источники
- Школьная комбинаторика: P(n,k) = n!/(n−k)!, C(n,k) = n!/(k!(n−k)!), размещения с повторениями n^k, сочетания с повторениями C(n+k−1, k), полиномиальный коэффициент n!/(n₁! n₂! …).