Числа Каталана
Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.
Пусть [math]X[/math] — произвольная правильная скобочная последовательность длины [math]2n[/math] . Она начинается с открывающейся скобки. Найдем парную ей закрывающуюся скобку и представим последовательность [math]X[/math] в виде: [math]X = (A)B[/math] , где [math]A[/math] и [math]B[/math] — тоже правильные скобочные последовательности. Если длина последовательности [math]A[/math] равна [math]2k[/math] , то последовательность [math]A[/math] можно составить [math]C_k[/math] способами. Тогда длина последовательности [math]B[/math] равна [math]2(n — k — 1)[/math] и последовательность [math]B[/math] можно составить [math]C_[/math] способами. Комбинация любого способа составить последовательность [math]A[/math] с любым способом составить последовательность [math]B[/math] даст новую последовательность [math]X[/math] , а величина [math]k[/math] может меняться от [math]0[/math] до [math]n — 1[/math] . Получили рекуррентное соотношение: [math]C_n = C_0 C_ + C_1 C_ + \ldots + C_ C_0 [/math] . Так как [math]C_0 = 1[/math] , то последовательность совпадает с числами Каталана.
Аналитическая формула
[math] C_n = \dfrac \dbinom [/math]
Доказательство
Правильной скобочной структуре из [math]n[/math] открывающих и [math]n[/math] закрывающих скобок мы поставим в соответствие путь в квадрате [math][0, n]×[0, n][/math] . Путь начинается в точке [math](0,0)[/math] и заканчивается в точке [math](n, n)[/math] . Открывающей скобке мы сопоставляем горизонтальный отрезок длины [math]1[/math] , а закрывающей — вертикальный. Если путь сопоставлен правильной структуре, то ни одна его точка не может лежать выше главной диагонали квадрата. Обратно, такому пути («правильному пути») сопоставляется правильная скобочная структура. Геометрическое представление правильных скобочных структур позволяет найти выражение для чисел Каталана.
Сместим правильный путь на одну клетку вниз. Теперь правильный путь начинается в точке [math] (0, -1) [/math] , заканчивается в точке [math] (n, n-1) [/math] и не имеет общих точек с прямой [math] y = x [/math] — биссектрисой первого квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных, и из общего числа путей вычтем количество неправильных. Мы рассматриваем пути из точки [math] (0, -1) [/math] в точку [math] (n, n-1) [/math] . Длина такого пути равна [math]2n[/math] и он содержит [math]n[/math] вертикальных сегментов и [math]n[/math] горизонтальных. Количество всех таких путей равно числу способов выбрать [math]n[/math] вертикальных сегментов из общего числа [math]2n[/math] сегментов, т.е. равно [math] \dbinom [/math] .
Рассмотрим неправильный путь и его первую точку на прямой [math] y = x [/math] (точка [math]A[/math] ). Отрезок пути от точки [math](0, -1)[/math] до точки [math]A[/math] заменим симметричным относительно прямой [math]y = x[/math] . Мы получим путь длины [math]2n[/math] , идущий из точки [math](-1, 0)[/math] в точку [math](n, n-1)[/math] (Смотри рис.).
Такой путь обязательно пересекает прямую [math] y = x [/math] . Обратно, пусть нам дан путь длины [math] 2n [/math] из точки [math](-1, 0)[/math] в точку [math](n, n-1)[/math] и пусть [math] A [/math] — первая точка этого пути, лежащая на прямой [math]y = x[/math] . Заменив участок пути от точки [math](-1, 0)[/math] до точки [math]A[/math] на симметричный относительно прямой [math]y = x[/math] , мы получим неправильный путь из точки [math](0, -1)[/math] в точку [math](n, n-1)[/math] . Следовательно, неправильных путей из точки [math](0, -1)[/math] в точку [math](n, n-1)[/math] столько же, сколько путей из точки [math](-1, 0)[/math] в точку [math](n, n-1)[/math] . Такой путь длины [math]2n[/math] содержит [math]n+1[/math] горизонтальных и [math]n-1[/math] вертикальных участков. Поэтому, количество таких путей равно [math] \dbinom [/math] . Значит, количество правильных путей (т.е. число Каталана [math]C_n[/math] ) равно
Задача разбиения выпуклого [math] n [/math] —угольника на треугольники не пересекающимися диагоналями
Доказательство
Пусть [math]t_n[/math] — число триангуляций выпуклого [math] (n + 2) [/math] -угольника при [math] n \geqslant 1 [/math] . Положим [math] t_0 = 1 [/math] . Пронумеруем вершины многоугольника, начиная с произвольной против часовой стрелки. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне [math]01[/math] (см. рис.).
Пусть [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_ = t_0 t_n + t_1 t_ + \ldots + t_n t_0 [/math] и поскольку [math]t_0 = 1[/math] , последовательность чисел [math]t_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] .
Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем [math]5[/math] разных случаев. В первом и последнем из них количество разбиений равно [math]14[/math] , ибо после отрезания треугольника остаётся шестиугольник. Во втором и четвёртом случаях при вырезании треугольника семиугольник распадается на треугольник и пятиугольник. В третьем случае семиугольник распадается на два четырёхугольника. Поскольку каждый из них можно разбить двумя способами, получаем [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]O(n)[/math] памяти и [math]O(n^2)[/math] времени. За [math]O(n)[/math] времени их можно посчитать, если использовать аналитическую формулу. Также из аналитической формулы можно выразить простую реккурентную формулу:
Вычисление производящей функции чисел Каталана
| Задача: |
| Вычислить производящую функцию чисел Каталана |
Пусть мы имеем последовательность чисел Каталана [math](C_0, C_1, C_2, \ldots)[/math] .
Будем искать её производящую функцию в виде [math]G(z) = \sum\limits_^ <\infty>C_n \cdot z^n[/math]
Как известно, рекуррентное соотношение для чисел Каталана имеет вид
Домножаем [math]C_n[/math] на [math]z^n[/math] , получая
Суммируя [math]C_n z^n[/math] по всем [math]n[/math] от [math]0[/math] до [math]\infty[/math] , получаем:
[math]G(z) = \sum\limits_^ <\infty>C_n z^n = C_0 z^0 + \sum\limits_^<\infty>z^n \sum\limits_^ C_k C_ = C_0 + \sum\limits_^<\infty>z^n \sum\limits_^ C_k C_ = 1 + \sum\limits_^<\infty>z^n \sum\limits_^ C_k C_[/math] (так как [math]C_0 = 1[/math] по определению чисел Каталана).
Получили, что [math]G(z) = 1 + \sum\limits_^<\infty>z^n \sum\limits_^ C_k C_~~~~~ \textbf[/math]
Распишем произведение [math]G(z) \cdot G(z)[/math] по определению произведения формальных степенных рядов.
[math]G(z) \cdot G(z) = (\sum\limits_^ <\infty>C_n z^n) \cdot (\sum\limits_^ <\infty>C_n z^n) = \sum\limits_^<\infty>z^n \sum\limits_^ C_k C_[/math]
В последнем выражении выполним сдвиг индексации, положив [math]n’ = n + 1[/math] . Тогда имеем: [math]n = n’ — 1, n = 0 \Rightarrow n’ = 1[/math] . Кроме того, [math]z^n = z^[/math] . [math]n — k[/math] преобразуется в [math]n’ — 1 — k[/math] (так как [math]n’ — 1 = n[/math] ). Тогда, преобразуя предыдущее выражение, получаем:
Домножая это произведение на [math]z[/math] , получаем
Из [math] \textbf[/math] и [math]\textbf[/math] получаем:
[math]G(z) = 1 + z \cdot G^2(z)[/math]
Преобразуя, получаем квадратное уравнение на [math]G(z) :[/math]
[math]z \cdot G^2(z) — G(z) + 1 = 0[/math]
Из этого квадратного уравнения находим два варианта [math]G(z) :[/math]
Выберем из двух корней тот, который удовлетворяет определению [math]G(z)[/math] как производящей функции чисел Каталана.
Домножая обе части на [math]2z[/math] , получаем [math]G(z) \cdot 2z = 1 \pm \sqrt ~~~~~\textbf[/math]
Выберем нужный из двух корней, посчитав значение обеих частей при [math]z = 0[/math]
Из определения производящей функции для чисел Каталана известно, что [math]G(z) = C_0 + C_1 \cdot x + \ldots + C_n \cdot x^n + \ldots[/math] , тогда [math]G(0) = C_0 = 1[/math]
Тогда при [math]z = 0[/math] выражение [math]\textbf[/math] принимает вид [math]G(0) \cdot 2 \cdot 0 = 1 \pm \sqrt[/math] , или [math]0 = 1 \pm 1[/math] .
Тогда очевидно, нужно выбрать знак [math]-[/math] в выражении, чтобы при [math]z = 0[/math] левая и правая части были равны.
Проверим, что [math]G(z)[/math] действительно является производящей функцией чисел Каталана. Для этого разложим [math]G(z)[/math] в ряд.
Тогда коэффициент при [math]z^n[/math] в разложении [math]G(z)[/math] равен [math]\dfrac \cdot \dbinom[/math] , что совпадает с аналитической формулой для чисел Каталана. ( [math]C_n = \dfrac \cdot \dbinom[/math] ) Поэтому [math]G(z) = \sum\limits_^ <\infty>z^n \cdot C_n[/math] , поэтому [math]G(z) = \dfrac>[/math] является производящей функцией чисел Каталана.
Смотри также
Источники информации
Источник
Числа Каталана
Пусть G=(V,E) – простой граф. Напомним, что две вершины, принадлежащие одному ребру, называются смежными. Элементарным путем длины n в графе G, соединяющим вершины p и q, называется последовательность вершин (v0, v1, × × ×, vn) таких, что
Элементарным циклом длины n в графе G называется последовательность вершин (v0, v1, × × ×, vn) таких, что
Элементарный цикл можно интерпретировать как непрерывный замкнутый путь в графе, не имеющий кратных вершин. Простой граф, не имеющий элементарных циклов длины >0, называется деревом. Дерево с выделенной вершиной называется корневым, а выделенная вершина – его корнем.
Для каждой вершины q существует единственный элементарный путь, соединяющий ее с корнем. Длина этого пути называется высотой вершины q. Смежные с q вершины, высота которых больше высоты вершины q на 1, называются детьми вершины q. На рис. 4.5 показано дерево с корнем 3.
Определение 1. Корневое дерево, каждая вершина которого имеет не более двух детей, называется бинарным, если детям приписан дополнительный признак ‘левой’ или ‘правой’ смежной вершины. Вершина не может иметь две левые или две правые смежные вершины. Бинарное дерево вместе с функцией, сопоставляющей каждой вершине некоторое число, называется бинарным деревом чисел.
Бинарное дерево чисел можно определить по индукции:
(1) Пустое дерево является бинарным деревом чисел.
(2) Если T1 и T2 – бинарные деревья чисел, то (T1, число, T2) – бинарное дерево чисел.
Определим отношение эквивалентности на множестве бинарных деревьев чисел S~T следующим образом.
(1) Если S=T=Æ, то S~T.
Число классов эквивалентности бинарных деревьев имеющих n вершин называется n -м числом Каталана и обозначается через cn.
На рис. 4.6 показаны классы эквивалентности бинарных деревьев, имеющих n вершин, при n=0, 1, 2, 3:
Пример 1. Число расстановок скобок. Пусть ‘*’ — бинарная операция на множестве A, которая не предполагается ни коммутативной, ни ассоциативной. Терм определяется по индукции. В нормальной форме Бэкуса-Наура определение будет следующим:
Здесь aÎA – произвольный элемент. Например, термами являются слова: (a*a)*b, a*(b*c), и т.д. Число термов, содержащих n операций *, равно cn.
Изображенным на рисунке бинарным деревьям соответствуют термы:
Пример 2. Деревом поиска называется бинарное дерево, вершинам которого соответствуют элементы некоторого линейно упорядоченного множества. Причем для каждой вершины значение в ней не меньше значений в вершинах левого поддерева и больше значений в вершинах правого поддерева. Элементы возрастающей последовательности n чисел можно расположить в узлах дерева поиска. Оно будет бинарным деревом и может быть выбрано cn способами.
Теорема 1. Числа Каталана равны .
Доказательство. Имеют место соотношения для чисел классов бинарных деревьев:
Пусть C(x) = — производящая функция последовательности чисел Каталана.
Получаем C(x) = xC 2 (x)+1, откуда .
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник