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

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

Числа Каталана — последовательность чисел, выражающих:

количество не изоморфных упорядоченных бинарных деревьев с корнем и [math] n + 1 [/math] листьями
количество способов соединения [math] 2n [/math] точек на окружности [math] n [/math] не пересекающимися хордами
количество триангуляций выпуклого [math] n [/math]-угольника
количество способов полностью разделить скобками [math] n + 1 [/math] множитель
количество корректных скобочных последовательностей, состоящих из [math] n [/math] открывающих и [math] 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] )( [/math] и [math] ((())))( [/math] — неправильные.) Эти два условия не только необходимы, но и достаточны.

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

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

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

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

Самой левой открывающей скобке [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] n \times n [/math] равно [math] \binom {n}{2n} [/math]. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке [math] (n - 1) \times (n + 1) [/math]. Но, с другой стороны, любой монотонный путь в решётке [math] (n - 1) \times (n + 1) [/math] обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке [math] n \times n[/math]. Монотонных путей в решётке [math](n - 1) \times (n + 1)[/math] имеется [math] \binom {n-1} {2n} [/math]. В результате получаем формулу:

Источники

</wikitex>

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