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

Пусть G=(V,E) – простой граф. Напомним, что две вершины, принадлежащие одному ребру, называются смежными. Элементарным путем длины n в графе G, соединяющим вершины p и q, называется последовательность вершин (v₀, v₁, × × ×, v_n) таких, что

_· p=v₀ и q=v_n;

_· v_i и v_i₊₁ смежны, "iÎ{0,1, × × ×, n-1};

_· v_i =v_j Þ i=j.

Элементарным циклом длины n в графе G называется последовательность вершин (v₀, v₁, × × ×, v_n) таких, что

_· v₀ =v_n;

_· v_i и v_i₊₁ смежны, "iÎ{0,1, × × ×, n-1};

_· v_i =v_j Þ (i=j Ú {i,j}={0,n}).

Элементарный цикл можно интерпретировать как непрерывный замкнутый путь в графе, не имеющий кратных вершин. Простой граф, не имеющий элементарных циклов длины >0, называется деревом. Дерево с выделенной вершиной называется корневым, а выделенная вершина – его корнем.

Рис. 4.5. Корневое дерево

Для каждой вершины q существует единственный элементарный путь, соединяющий ее с корнем. Длина этого пути называется высотой вершины q. Смежные с q вершины, высота которых больше высоты вершины q на 1, называются детьми вершины q. На рис. 4.5 показано дерево с корнем 3.

Определение 1. Корневое дерево, каждая вершина которого имеет не более двух детей, называется бинарным, если детям приписан дополнительный признак ‘левой’ или ‘правой’ смежной вершины. Вершина не может иметь две левые или две правые смежные вершины. Бинарное дерево вместе с функцией, сопоставляющей каждой вершине некоторое число, называется бинарным деревом чисел.

Бинарное дерево чисел можно определить по индукции:

(1) Пустое дерево является бинарным деревом чисел.

(2) Если T₁ и T₂ – бинарные деревья чисел, то (T₁, число, T₂) – бинарное дерево чисел.

Определим отношение эквивалентности на множестве бинарных деревьев чисел S~T следующим образом.

(1) Если S=T=Æ, то S~T.

(2) Если S=(S₁, m, S₂), T=(T₁, n, T₂), S₁~ T₁и S₂~ T₂, то S~T.

Число классов эквивалентности бинарных деревьев имеющих n вершин называется n -м числом Каталана и обозначается через c_n.

На рис. 4.6 показаны классы эквивалентности бинарных деревьев, имеющих n вершин, при n=0, 1, 2, 3:

Рис. 4.6. Бинарные деревья.

Пример 1. Число расстановок скобок. Пусть ‘*’ - бинарная операция на множестве A, которая не предполагается ни коммутативной, ни ассоциативной. Терм определяется по индукции. В нормальной форме Бэкуса-Наура определение будет следующим:

Терм::= a | (Терм*Терм)

Здесь aÎA – произвольный элемент. Например, термами являются слова: (a*a)*b, a*(b*c), и т.д. Число термов, содержащих n операций *, равно c_n.

Изображенным на рисунке бинарным деревьям соответствуют термы:

(1) a,

(2) (a*b),

(3) ((a*b)*c), (a*(b*c)),

(4) (a*((b*c)*d)), (a*(b*(c*d))), ((a*b)*(c*d)), (((a*b)*c)*d), ((a*(b*c))*d).

Пример 2. Деревом поиска называется бинарное дерево, вершинам которого соответствуют элементы некоторого линейно упорядоченного множества. Причем для каждой вершины значение в ней не меньше значений в вершинах левого поддерева и больше значений в вершинах правого поддерева. Элементы возрастающей последовательности n чисел можно расположить в узлах дерева поиска. Оно будет бинарным деревом и может быть выбрано c_n способами.