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

2014-10-18T21:03:32Z

5.18.60.172:

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

<wikitex>
{{Определение
|id = def1
|definition =Числа Каталана {{---}} последовательность чисел, выражающих:
*количество не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями;
*количество способов соединения $2n$ точек на окружности $n$ не пересекающимися хордами;
*количество разбиений выпуклого $n$-угольника на треугольники не пересекающимися диагоналями;
*количество способов полностью разделить скобками $n + 1$ множитель;
*количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;}}

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

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...
</wikitex>

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

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

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

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

==Рекуррентная формула чисел Каталана==
<wikitex>
<tex dpi = "170"> C_n = \frac{(2n-2)!}{n!(n-1)!} </tex>

===Доказательство формулы===

При доказательстве будем использовать производящие функции. Идея состоит в том, чтобы "запаковать"всю бесконечную последовательность в одно выражение. Производящая функция для последовательности Каталана 1, 1, 2, 5, 14, 42, 132, ... - это функция:

<tex dpi = "140"> f (x) = 1 + {x} + {x}^2 + 2{x}^3 + 5{x}^4 + 14{x}^5 + 42{x}^6 + 132{x}^7 + 429{x}^8 + 1430{x}^9 + ...</tex>

При этом нас даже не интересует, для каких $x$ этот степенной ряд сходится, так как мы рассматриваем только формальный степенной ряд . Возведем его в квадрат и получим:

<tex dpi = "140"> f (x)*f (x) = </tex>
</wikitex>

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

2014-10-18T19:24:33Z

5.18.60.172: /* Задача разбиения выпуклого $n$-угольника на треугольники не пересекающимися диагоналями */

Викиконспекты - Вклад участника [ru]

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

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