АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. III. ОСНОВНЫЕ АКСИОМЫ ЧИСЛА (ЧИСЛО КАК СУЖДЕНИЕ)
  2. Алгебраїчна форма запису комплексних чисел та дії над комплексними числами, записаними у цій формі
  3. Алгебраїчна форма комплексного числа
  4. Алгоритм получения дополнительного k-разрядного кода отрицательного числа
  5. Анализируемое жирное масло имеет величину йодного числа – 140. К какой группе жиров по высыхаемости оно относится?
  6. Аномалии числа хромосом
  7. Арифметические действия над двоичными числами
  8. Арифметические операции над двоично-десятичными числами
  9. Б1 2. Линейный оператор в конечномероном пространстве, его матрица. Характеристический многочлен линейного оператора. Собственные числа и собств векторы.
  10. Байта орнамента числа числа
  11. Билет 3 Комплексные числа в алгебраическом виде, операции над ними.
  12. Билет 40. Сингулярные числа и сингулярные векторы. Полярное разложение оператора (матрицы).

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

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

 

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

 

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

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

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

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

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

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

(2) Если S=(S1, m, S2), T=(T1, n, T2) , S1~ T1 и S2~ T2 , то S~T.

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

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

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

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

· для всякого элемента aÎA слово a есть терм;

· если t1 и t2 – термы, то (t1* t2) – терм.

В нормальной форме Бэкуса-Наура определение будет следующим:

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

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

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



(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 чисел можно расположить в узлах дерева поиска . Оно будет бинарным деревом и может быть выбрано cn способами.

Теорема 1. Числа Каталана равны .

Доказательство. Имеют место соотношения для чисел классов бинарных деревьев:

ck = c0ck-1 + c1ck-2 + ∙ ∙ ∙ +ck-1c0 , для всех k>0.

Пусть C(x) = - производящая функция последовательности чисел Каталана.

Получаем C(x) = xC2(x)+1, откуда .


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |


При использовании материала, поставите ссылку на Студалл.Орг (0.006 сек.)