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

Числа Каталана — це числова послідовність, яка виявляється корисною в багатьох комбінаторних задачах, часто пов'язаних з рекурсивно визначеними об'єктами.

Цю послідовність назвали на честь бельгійського математика Каталана, який жив у 19 столітті. (Насправді ж вона була відома ще раніше Ейлеру, який жив на століття раніше за Каталана).

Перші кілька чисел Каталана $C_n$ (починаючи з нуля):

$1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$

Коли підходить цей алгоритм?

• Чи відповіді на малих $n$ дають послідовність $1, 1, 2, 5, 14, 42$? Тоді це майже напевно числа Каталана.
• Чи задача про підрахунок збалансованих рекурсивних структур — правильних дужкових послідовностей, бінарних дерев, тріангуляцій многокутника, неперетинних хорд/розбиттів?
• Чи треба лише порахувати кількість, а не згенерувати самі об'єкти? (якщо ні → Генерування комбінацій або Дужкові послідовності)

Застосування в деяких комбінаторних задачах

Число Каталана $C_n$ є розв'язком для:

• Кількість правильних дужкових послідовностей, що складаються з $n$ відкривних і $n$ закривних дужок.
• Кількість кореневих повних двійкових дерев із $n + 1$ листком (вершини не нумеровані). Кореневе двійкове дерево називається повним, якщо кожна вершина має або двох нащадків, або жодного.
• Кількість способів повністю розставити дужки навколо $n + 1$ множників.
• Кількість тріангуляцій опуклого многокутника з $n + 2$ сторонами (тобто кількість розбиттів многокутника на неперетинні трикутники за допомогою діагоналей).
• Кількість способів з'єднати $2n$ точок на колі так, щоб утворити $n$ неперетинних хорд.
• Кількість неізоморфних повних двійкових дерев із $n$ внутрішніми вузлами (тобто вузлами, які мають хоча б одного нащадка).
• Кількість монотонних шляхів на ґратці з точки $(0, 0)$ до точки $(n, n)$ у квадратній ґратці розміру $n \times n$, які не проходять вище головної діагоналі (тобто тієї, що з'єднує $(0, 0)$ з $(n, n)$).
• Кількість перестановок довжини $n$, які можна відсортувати стеком (тобто можна показати, що перестановку можна відсортувати стеком тоді й лише тоді, коли не існує таких індексів $i < j < k$, що $a_k < a_i < a_j$ ).
• Кількість неперетинних розбиттів множини з $n$ елементів.
• Кількість способів покрити драбинку $1 \ldots n$ за допомогою $n$ прямокутників (драбинка складається з $n$ стовпців, де $i^{th}$ стовпець має висоту $i$).

Обчислення

Існують дві формули для чисел Каталана: рекурсивна та аналітична. Оскільки ми вважаємо, що всі згадані вище задачі еквівалентні (мають той самий розв'язок), то для доведення наведених нижче формул ми обиратимемо ту задачу, з якою це зробити найпростіше.

Рекурсивна формула

$$C_0 = C_1 = 1$$ $$C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 2$$

Рекурентну формулу легко вивести із задачі про правильну дужкову послідовність.

Найлівіша відкривна дужка $l$ відповідає певній закривній дужці $r$, яка ділить послідовність на 2 частини, кожна з яких, своєю чергою, теж має бути правильною дужковою послідовністю. Таким чином, формула теж ділиться на 2 частини. Якщо ми позначимо $k = {r - l - 1}$, то для фіксованого $r$ існуватиме рівно $C_k C_{n-1-k}$ таких дужкових послідовностей. Підсумувавши це за всіма допустимими $k$, ми отримуємо рекурентне співвідношення для $C_n$.

Можна міркувати й так. За означенням $C_n$ позначає кількість правильних дужкових послідовностей. Тепер послідовність можна поділити на 2 частини довжини $k$ і ${n - k}$, кожна з яких має бути правильною дужковою послідовністю. Приклад:

$( ) ( ( ) )$ можна поділити на $( )$ та $( ( ) )$, але не можна поділити на $( ) ($ та $( ) )$. Знову ж таки, підсумувавши за всіма допустимими $k$, ми отримуємо рекурентне співвідношення для $C_n$.

Реалізація на C++

C++

const int MOD = ....
const int MAX = ....
int catalan[MAX];
void init() {
    catalan[0] = catalan[1] = 1;
    for (int i=2; i<=n; i++) {
        catalan[i] = 0;
        for (int j=0; j < i; j++) {
            catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD;
            if (catalan[i] >= MOD) {
                catalan[i] -= MOD;
            }
        }
    }
}

Python

MOD = ...  # модуль
MAX = ...  # верхня межа
catalan = [0] * MAX
def init():
    catalan[0] = catalan[1] = 1
    for i in range(2, n + 1):
        catalan[i] = 0
        for j in range(i):
            catalan[i] += (catalan[j] * catalan[i - j - 1]) % MOD
            if catalan[i] >= MOD:
                catalan[i] -= MOD

TypeScript

const MOD = ...; // модуль
const MAX = ...; // верхня межа
const catalan: number[] = new Array(MAX).fill(0);
function init(): void {
  catalan[0] = catalan[1] = 1;
  for (let i = 2; i <= n; i++) {
    catalan[i] = 0;
    for (let j = 0; j < i; j++) {
      catalan[i] += (catalan[j] * catalan[i - j - 1]) % MOD;
      if (catalan[i] >= MOD) {
        catalan[i] -= MOD;
      }
    }
  }
}

Go

const MOD = ... // модуль
const MAX = ... // верхня межа
var catalan [MAX]int
func init() {
    catalan[0], catalan[1] = 1, 1
    for i := 2; i <= n; i++ {
        catalan[i] = 0
        for j := 0; j < i; j++ {
            catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD
            if catalan[i] >= MOD {
                catalan[i] -= MOD
            }
        }
    }
}

Аналітична формула

$$C_n = \frac{1}{n + 1} {\binom{2n}{n}}$$

(тут $\binom{n}{k}$ позначає звичайний біноміальний коефіцієнт, тобто кількість способів вибрати $k$ об'єктів із множини з $n$ об'єктів).

Наведену вище формулу легко вивести із задачі про монотонні шляхи у квадратній ґратці. Загальна кількість монотонних шляхів у ґратці розміру $n \times n$ дорівнює $\binom{2n}{n}$.

Тепер порахуємо кількість монотонних шляхів, які перетинають головну діагональ. Розглянемо такий шлях, що перетинає головну діагональ, і знайдемо в ньому перше ребро, яке лежить вище діагоналі. Відобразимо шлях відносно діагоналі на всій його частині після цього ребра. Результатом завжди буде монотонний шлях у ґратці $(n - 1) \times (n + 1)$. З іншого боку, будь-який монотонний шлях у ґратці $(n - 1) \times (n + 1)$ обов'язково перетинає діагональ. Отже, ми перелічили всі монотонні шляхи, які перетинають головну діагональ у ґратці $n \times n$.

Кількість монотонних шляхів у ґратці $(n - 1) \times (n + 1)$ дорівнює $\binom{2n}{n-1}$ . Назвемо такі шляхи «поганими». Як наслідок, щоб отримати кількість монотонних шляхів, які не перетинають головну діагональ, ми віднімаємо наведені вище «погані» шляхи, отримуючи формулу:

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

Джерела

• Catalan Number by Tom Davis

Задачі для практики

• Codechef - PANSTACK
• Spoj - Skyline
• UVA - Safe Salutations
• Codeforces - How many trees?
• SPOJ - FUNPROB

• LOJ - 1170 - Counting Perfect BST
• UVA - 12887 - The Soldier's Dilemma

Відеоматеріали