- PVSM.RU - https://www.pvsm.ru -
Несомненно, самым замечательным математическим фактом является тождество . В нем удивительным образом сошлись, казалось бы, совершенно не связанные константы из разных областей математики. Доказать это тождество не так сложно, но объяснить его, понять глубинный смысл, удается немногим.
В качестве еще одного замечательного факта хотелось бы вспомнить числа Каталана, которые удивительным образом всплывают в самых разных комбинаторных задачах. К сожалению, они выпадают из рассмотрения типовой школьной программы, но уверен, что любой специалист компьютерных наук должен быть знаком с ними.
Само число Каталана выражается формулой C(n) = (2n)!/n!(n+1)!, где восклицательный знак, как обычно, обозначает факториал. Начало последовательности выглядит так: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…
Английская Википедия [1] утверждает, что известно, как минимум 66 различных конструкций, которые приводят к появлению чисел Каталана. Вот некоторые из них:
Для каждой из этих конструкций можно либо по индукции, либо реккурентными соотношениями доказать, что число соответствующих объектов выражается числом Каталана. Не буду останавливаться на этих доказательствах – их можно найти в учебниках по дискретной математике. Также есть некоторые замечательные соотношения, которые можно получить, используя некоторые из упомянутых построений. Но это требует написания громоздких формул, чего хотелось бы избежать. Сейчас интереснее другое – неужели совпадение всех этих количеств для совершенно разных вещей случайность?
Конечно же, нет. Связь этих конструкций гораздо глубже. Можно построить взаимнооднозначное соответствие между этими объектами и некоторые из таких соответствий я попробую продемонстрировать. Помимо простого любопытства это имеет и некоторую практическую ценность. Например, задачу о генерации всех бинарных деревьев (решение которой в лоб неочевидно) можно свести к гораздо более простой задаче о генерации скобочных последовательностей.
Очень легко построить соответствие между скобочными последовательностями и монотонными путями в квадрате. Читая скобочную последовательность слева направо, будем строить путь, начав из левого нижнего угла, – для каждой открывающейся скобки нарисуем горизонтальный отрезок, для закрывающейся скобки – вертикальный.
Так как в последовательности было равное число открывающихся и закрывающихся скобок, то путь в итоге закончится в правом верхнем углу, а тот факт, что каждая открывающаяся скобка стоит раньше соответствующей ей закрывающейся скобки (ведь последовательность — правильная) гарантирует нам, что путь не перейдет в верхнюю половину квадрата. Очевидно, что это построение обратимо и из каждого монотонного пути можно получить скобочную последовательность.
На приведенном рисунке соответствующие скобки и отрезки отмечены одним цветом. Хорошо заметно, что отрезки, соответствующие одной паре скобок «видят друг друга»:
В качестве второй задачи построим соответствие между правильными скобочными последовательностями и таблицами Юнгам 2xn. Тут тоже все просто. Пронумеруем скобки слева направо. Если скобка открывающаяся, то соответствующее ей число пишем в верхнюю строку. Если закрывающаяся, то в – нижнюю. Так как i-ая открывающаяся скобка всегда стоит левее i-ой закрывающейся, то число соответствующее открывающейся скобке будет меньше числа, соответствующего закрывающей. А значит, верхнее число в таблице окажется меньше нижнего в той же колонке, то есть из правильной скобочной последовательности мы получили таблицу Юнга. Это построение также обратимо, а значит получено взаимно-однозначное соответствие.
Теперь займемся бинарными деревьями. Очень легко увидеть соответствие между бинарными деревьями и расстановками скобок в выражении с однородными операциями, но это дает несколько другие последовательности. Для привязки бинарных деревьев к правильным скобочным последовательностям надо воспользоваться несколько другим подходом. Воспользуемся стандартным обходом дерева и пронумеруем вершины (корень примем за 0) в порядке обхода. Теперь, если при переходе к числу I мы спустились от родителя к ребенку, то на i-ое место ставим открывающуюся скобку. В противном случае ставим закрывающуюся.
Дерево – бинарное, поэтому у каждого узла есть сосед. А значит, спустившись к ребенку и поставив открывающуюся скобку, мы рано или поздно доберемся до его соседа и поставим закрывающуюся скобку. Это гарантирует правильность получившейся последовательности. Построение легко обратить и взяв за основу скобочную последовательность получить бинарное дерево.
Заметим, что если в скобочной последовательности n пар то соответствующее дерево имеет n+1 лист.
Для построения соответствия между триангуляциями многоугольника проще всего использовать бинарное дерево. На этот раз мы занумеруем в нем все листья слева направо (остальные узлы пометим буквами). Для триангуляции возьмем многоугольник, в котором вершин на одну больше, чем листьев в дереве. Одну из сторон этого многоугольника отметим, как стартовую, а остальные занумеруем (для наглядности – против часовой стрелки).
Далее выполняем следующую процедуру – если два вершины дерева соседние, то соответствующие стороны многоугольника «стянем» диагональю, которую пометим той буквой, которой помечен родитель этой пары узлов в дереве. Далее продолжаем процедуру «стягивания» пока от многоугольника не останется единственный стартовый отрезок.
Как можно заметить три стороны каждого треугольника в получившемся разбиении соответствуют одному родительскому узлу и двум его потомкам. Поэтому, если взять два разных дерева, то получится два разных разбиения.
Ну и в заключение приведу табличку, в котором изображено соответствие объектов для третьего числа Каталана.
Автор: bay73
Источник [4]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/24438
Ссылки в тексте:
[1] Английская Википедия : http://en.wikipedia.org/wiki/Catalan_number
[2] уже обсуждались : http://habrahabr.ru/post/93506/
[3] обсуждались : http://habrahabr.ru/post/93633/
[4] Источник: http://habrahabr.ru/post/165295/
Нажмите здесь для печати.