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

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

Определение:

Числа Каталана — последовательность чисел, выражающих: количество не изоморфных упорядоченных бинарных деревьев с корнем и [math] n + 1 [/math] листьями количество способов соединения [math] 2n [/math] точек на окружности [math] n [/math] не пересекающимися хордами количество триангуляций выпуклого [math] n [/math]-угольника количество способов полностью разделить скобками [math] n + 1 [/math] множитель количество корректных скобочных последовательностей, состоящих из [math] n [/math] открывающих и [math] n [/math] закрывающих скобок

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

[math] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ... [/math]

Рекуррентная формула чисел Каталана

[math]C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i} [/math]

Доказательство

Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.

Самой левой открывающей скобке [math] l [/math] соответствует определённая закрывающая скобка [math] r [/math], которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим [math] i = r - l - 1 [/math], то для любого фиксированного [math] r [/math] будет ровно [math] C_i C_{n-1-i} [/math] способов. Суммируя это по всем допустимым [math] i [/math], мы и получаем рекуррентную зависимость на [math] C_n [/math].

Аналитическая формула

[math] C_n = \frac{1}{n+1} \binom {2n} {n} [/math]

Доказательство

Сместим правильный путь на 1 клетку вниз. Теперь правильный путь начинается в точке [math] (0, −1) [/math], заканчивается в точке [math] (n, n − 1) [/math] и не имеет общих точек с прямой [math] y = x [/math] — биссектрисой первого квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных, и из общего числа путей вычтем количество неправильных. Мы рассматриваем пути из точки [math] (0, −1) [/math] в точку [math] (n, n − 1) [/math]. Длина такого пути равна 2n и он содержит n вертикальных сегментов и n горизонтальных. Количество всех таких путей равно числу способов выбрать n вертикальных сегментов из общего числа 2n сегментов, т.е. равно [math] \binom {n}{2n} [/math]. Рассмотрим неправильный путь и его первую точку на прямой [math] y = x [/math] (точка A). Отрезок пути от точки (0, −1) до точки A заменим симметричным относительно прямой y = x. Мы получим путь длины 2n, идущий из точки (−1, 0) в точку (n, n − 1). Такой путь обязательно пересекает прямую y = x. Обратно, пусть нам дан путь длины 2n из точки (−1, 0) в точку (n, n − 1) и пусть A — первая точка этого пути, лежащая на прямой y = x. Заменив участок пути от точки (−1, 0) до точки A на симметричный относительно прямой y = x, мы получим неправильный путь из точки (0, −1) в точку (n, n − 1). Следова- тельно, неправильных путей из точки (0, −1) в точку (n, n − 1) столько же, сколько путей из точки (−1, 0) в точку (n, n−1). Такой путь длины содержит n+ 1 горизонтальных и n−1 вертикальных участков. Поэтому, количество таких путей равно C n−1 2n. Значит, количество правильных путей (т.е. число Каталана Cn) равно

[math] C_n = \binom {2n} {n} - \binom {2n} {n-1} = \frac{1}{n+1} \binom {2n} {n} [/math]

Примеры

Задача разбиения выпуклого [math] n [/math]—угольника на треугольники не пересекающимися диагоналями

Разбиение выпуклого шестиугольника

Ответ на задачу при [math] n = 3 [/math] тривиален: никаких диагоналей проводить не надо. В четырёхугольнике можно провести любую из двух диагоналей, так что способов два. В пятиугольнике — из любой вершины две диагонали, [math] 5 [/math] способов. При [math] n = 6 [/math] — первый не вполне очевидный ответ: [math] 14 [/math] способов (см. рис.); чтобы не запутаться, сторона BC выделена и отдельно нарисованы разрезания, в которых к ней примыкают соответственно треугольники [math] BCA, BCF, BCE [/math] и [math] BCD [/math].

Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем 5 разных случаев. В первом и последнем из них количество разбиений равно 14, ибо после отрезания треугольника остаётся шестиугольник. Во втором и четвёртом случаях при вырезании треугольника семиугольник распадается на треугольник и пятиугольник. В третьем случае семиугольник распадается на два четырёхугольника. Поскольку каждый из них можно разбить двумя способами, получаем [math]2 \cdot 2 = 4[/math] варианта. Итак, семиугольник можно разбить всего [math] 14 + 5 + 2 \cdot 2 + 5 + 14 = 42 [/math] способами. Рассматривая восьмиугольник, аналогично получаем [math] 42 + 14 + 2 \cdot 5 + 5 \cdot 2 + 14 + 42 = 132 [/math] способа.Такие вычисления можно проводить и дальше.

Доказательство

Пусть [math]t_n[/math] — число триангуляций [math] (n + 2) [/math] угольника при [math] n \gt = 1 [/math]; положим [math] t_0 [/math] = 1. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне 01 (см. рис.).

Пусть [math]k[/math] — номер третьей вершины этого треугольника. Выделенный треугольник разбивает [math](n + 2)[/math]-угольник на [math]k[/math]-угольник и [math](n-k+3)[/math]-угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций [math]k[/math]-угольника и [math](n-k+3)[/math]-угольника. Наоборот, каждая пара триангуляций [math]k[/math]-угольника и [math](n-k+3)[/math]-угольника определяет триангуляцию исходного многоугольника. Поэтому [math]t_{n+1} = t_0 t_n + t_1 t_{n-1} + \cdot \cdot \cdot + t_n t_0 [/math] и поскольку [math]t_0[/math] = 1, последовательность чисел [math]t_n[/math] совпадает с последовательностью Каталана.

Задача расстановки скобок

Рассмотрим какое-нибудь арифметическое выражение и сотрём всё, кроме скобок. Получим некоторую систему открывающих и закрывающих скобок. Какими свойствами она обладает? Во-первых, открывающих скобок ровно столько же, сколько и закрывающих. Во-вторых, ни в каком начальном отрезке количество закрывающих скобок не может оказаться больше количества открывающих скобок. (Например, расстановки [math] )( [/math] и [math] ((())))( [/math] — неправильные.) Эти два условия не только необходимы, но и достаточны.

Рассмотрим несколько примеров. Одна пара скобок может выглядеть единственным способом: [math] () [/math]. Две пары — двумя способами: [math] ()() [/math] или [math] (()) [/math]. Три пары — пятью способами: [math] ()()(), ()(()), (())(), (()()) [/math] или [math] ((())) [/math]. Четыре пары, как нетрудно проверить,— четырнадцатью способам и. Чтобы понять, сколькими способами могут выглядеть правильно расставленные пять пар скобок, рассмотрим закрывающую скобку, парную к первой открывающей скобке. Остальные четыре пары тогда разделятся на две группы: расположенные внутри рассмотренной пары и расположенные справа от неё. (Разумеется, любая из этих групп может состоять из 0 скобок.) Способов, когда все четыре пары внутри или все четыре справа, имеется по 14 штук. Когда три пары внутри, а одна справа, имеем 5 способов. Столько же — когда одна внутри, а три справа. Наконец, когда две пары внутри, а две справа, имеем 2 · 2 = 4 способа. Итого [math] 14 + 5 + 2 \cdot 2 + 5 + 14 = 42 [/math] способа. Следуя такому походу, можно вычислять количество правильных скобочных последовательностей дальше.

Подсчет чисел Каталана

Будем вести подсчет с использованием метода динамического программирования. Пусть [math]d[i][j][/math] - число скобочных последовательностей длиной [math]i[/math] с балансом [math]j[/math]. Скобочную последовательность длиной [math]i[/math] с балансом [math]j[/math], можно получить из скобочной последовательности длины [math]i-1[/math] с балансом или [math]j-1[/math] (добавив в конец открывающуюся скобку), или [math]j+1[/math] (добавив в конец закрывающуюся скобку), т.е. [math]d[i][j] = d[i-1][j-1]+d[i-1][j+1][/math]. База [math]d[0][0][/math] = 1. Так же можно заметить, что максимальный баланс правильной скобочной последовательности длины [math]2n[/math], равен [math]n[/math]. Числа Каталана будут храниться в строке [math]j[/math] = 0.

Псевдокод:

d[0][0] = 1
for i = 1 to 2n
  for j = 0 to n
    d[i][j] = d[i-1][j-1] + d[i-1][j+1]

Таблица значений

Найдем значения таблицы для [math]n[/math] = 4

i\j	0	1	2	3	4	5	6	7	8
0	1	0	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0	0
2	1	0	1	0	0	0	0	0	0
3	0	2	0	1	0	0	0	0	0
4	2	0	3	0	1	0	0	0	0
5	0	5	0	4	0	0	0	0	0
6	5	0	9	0	4	0	0	0	0
7	0	14	0	13	0	0	0	0	0
8	14	0	27	0	13	0	0	0	0

Смотри также

<wikitex>

• Двоичное дерево поиска
• Триангуляция полигонов

</wikitex>

Источники

<wikitex>

• MAXimal :: algo :: Числа Каталана
• Числа Каталана / Хабрахабр
• Числа Каталана — Википедия
• Журнал "Квант"
• Глава 5. Комбинаторика

</wikitex>