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

Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Resources/Combinatorics/Числа Каталана

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

Введение

В этой главе мы изучаем числа Каталана, одну из самых важных последовательностей в комбинаторике.

Они появляются во многих задачах подсчёта, связанных с рекурсивными структурами, сбалансированными объектами и некрещивающимися конфигурациями.

Первые несколько чисел Каталана:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, \ldots

Внешние задачи

Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:

ATCODERC. Split and Maximize

,

2674440

,

9694845

,

…

Определение

Распространённые интерпретации

Число Каталана $C_n$ считает множество различных комбинаторных объектов. Некоторые из самых известных интерпретаций:

число правильных скобочных последовательностей с $n$ открывающими и $n$ закрывающими скобками;
число укоренённых полных двоичных деревьев с $n+1$ листьями;
число способов полностью расставить скобки в произведении из $n+1$ множителей;
число триангуляций выпуклого многоугольника с $n+2$ сторонами;
число способов соединить $2n$ точек на окружности с помощью $n$ непересекающихся хорд;
число монотонных решёточных путей из $(0,0)$ в $(n,n)$ , которые никогда не поднимаются выше главной диагонали;
число некрещивающихся разбиений множества из $n$ элементов.

Это очень разные задачи, но все они приводят к одной и той же последовательности.

Рекуррентная формула

Числа Каталана определяются рекурсивно:

C_0 = 1

и для $n \geq 1$ ,

C_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k}

Явная формула

Числа Каталана также имеют замкнутую формулу:

C_n = \frac{1}{n+1} \binom{2n}{n}, \quad n \geq 0