Несомненно, самым замечательным математическим фактом является тождество 
. В нем удивительным образом сошлись, казалось бы, совершенно не связанные константы из разных областей математики. Доказать это тождество не так сложно, но объяснить его, понять глубинный смысл, удается немногим.
В качестве еще одного замечательного факта хотелось бы вспомнить числа Каталана, которые удивительным образом всплывают в самых разных комбинаторных задачах. К сожалению, они выпадают из рассмотрения типовой школьной программы, но уверен, что любой специалист компьютерных наук должен быть знаком с ними.
Само число Каталана выражается формулой C(n) = (2n)!/n!(n+1)!, где восклицательный знак, как обычно, обозначает факториал. Начало последовательности выглядит так: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…
Английская Википедия утверждает, что известно, как минимум 66 различных конструкций, которые приводят к появлению чисел Каталана. Вот некоторые из них:
Для каждой из этих конструкций можно либо по индукции, либо реккурентными соотношен��ями доказать, что число соответствующих объектов выражается числом Каталана. Не буду останавливаться на этих доказательствах – их можно найти в учебниках по дискретной математике. Также есть некоторые замечательные соотношения, которые можно получить, используя некоторые из упомянутых построений. Но это требует написания громоздких формул, чего хотелось бы избежать. Сейчас интереснее другое – неужели совпадение всех этих количеств для совершенно разных вещей случайность?
Конечно же, нет. Связь этих конструкций гораздо глубже. Можно построить взаимнооднозначное соответствие между этими объектами и некоторые из таких соответствий я попробую продемонстрировать. Помимо простого любопытства это имеет и некоторую практическую ценность. Например, задачу о генерации всех бинарных деревьев (решение которой в лоб неочевидно) можно свести к гораздо более простой задаче о генерации скобочных последовательностей.
Очень легко построить соответствие между скобочными последовательностями и монотонными путями в квадрате. Читая скобочную последовательность слева направо, будем строить путь, начав из левого нижнего угла, – для каждой открывающейся скобки нарисуем горизонтальный отрезок, для закрывающейся скобки – вертикальный.
Так как в последовательности было равное число открывающихся и закрывающихся скобок, то путь в итоге закончится в правом верхнем углу, а тот факт, что каждая открывающаяся скобка стоит раньше соответствующей ей закрывающейся скобки (ведь последовательность — правильная) гарантирует нам, ч��о путь не перейдет в верхнюю половину квадрата. Очевидно, что это построение обратимо и из каждого монотонного пути можно получить скобочную последовательность.
На приведенном рисунке соответствующие скобки и отрезки отмечены одним цветом. Хорошо заметно, что отрезки, соответствующие одной паре скобок «видят друг друга»:
В качестве второй задачи построим соответствие между правильными скобочными последовательностями и таблицами Юнгам 2xn. Тут тоже все просто. Пронумеруем скобки слева направо. Если скобка открывающаяся, то соответствующее ей число пишем в верхнюю строку. Если закрывающаяся, то в – нижнюю. Так как i-ая открывающаяся скобка всегда стоит левее i-ой закрывающейся, то число соответствующее открывающейся скобке будет меньше числа, соответствующего закрывающей. А значит, верхнее число в таблице окажется меньше нижнего в той же колонке, то есть из правильной скобочной последовательности мы получили таблицу Юнга. Это построение также обратимо, а значит получено взаимно-однозначное соответствие.
Теперь займемся бинарными деревьями. Очень легко увидеть соответствие между бинарными деревьями и расстановками скобок в выражении с однородными операциями, но это дает несколько другие последовательности. Для привязки бинарных деревьев к правильным скобочным последовательностям надо воспользоваться несколько другим подходом. Воспользуемся стандартным обходом дерева и пронумеруем вершины (корень примем за 0) в порядке обхода. Теперь, если при переходе к числу I мы спустились от родителя к ребенку, то на i-ое место ставим открывающуюся скобку. В противном случае ставим закрывающуюся.
Дерево – бинарное, поэтому у каждого узла есть сосед. А значит, спустившись к ребенку и поставив открывающуюся скобку, мы рано или поздно доберемся до его соседа и поставим закрывающуюся скобку. Это гарантирует правильность получившейся последовательности. Построение легко обратить и взяв за основу скобочную последовательность получить бинарное дерево.
Заметим, что если в скобочной последовательности n пар то соответствующее дерево имеет n+1 лист.
Для построени�� соответствия между триангуляциями многоугольника проще всего использовать бинарное дерево. На этот раз мы занумеруем в нем все листья слева направо (остальные узлы пометим буквами). Для триангуляции возьмем многоугольник, в котором вершин на одну больше, чем листьев в дереве. Одну из сторон этого многоугольника отметим, как стартовую, а остальные занумеруем (для наглядности – против часовой стрелки).
Далее выполняем следующую процедуру – если две вершины дерева соседние, то соответствующие стороны многоугольника «стянем» диагональю, которую пометим той буквой, которой помечен родитель этой пары узлов в дереве. Далее продолжаем процедуру «стягивания» пока от многоугольника не останется единственный стартовый отрезок.
Как можно заметить три стороны каждого треугольника в получившемся разбиении соответствуют одному родительскому узлу и двум его потомкам. Поэтому, если взять два разных дерева, то получится два разных разбиения.
Ну и в заключение приведу табличку, в котором изображено соответствие объектов для третьего числа Каталана.
. В нем удивительным образом сошлись, казалось бы, совершенно не связанные константы из разных областей математики. Доказать это тождество не так сложно, но объяснить его, понять глубинный смысл, удается немногим. В качестве еще одного замечательного факта хотелось бы вспомнить числа Каталана, которые удивительным образом всплывают в самых разных комбинаторных задачах. К сожалению, они выпадают из рассмотрения типовой школьной программы, но уверен, что любой специалист компьютерных наук должен быть знаком с ними.
Само число Каталана выражается формулой C(n) = (2n)!/n!(n+1)!, где восклицательный знак, как обычно, обозначает факториал. Начало последовательности выглядит так: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…
Английская Википедия утверждает, что известно, как минимум 66 различных конструкций, которые приводят к появлению чисел Каталана. Вот некоторые из них:
- Правильные скобочные последовательности – наборы открывающихся и закрывающихся скобок, в которых каждой открывающейся скобке соответствует закрывающаяся. Число возможных последовательностей с фиксированным числом пар скобок выражается числом Каталана. Например, 14 правильных последовательностей из четырех пар скобок:
(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(),
(())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()
- Двоичные деревья – деревья, из каждого узла которых (кроме листьев) выходит ровно две ветки. Количество бинарных деревьев с заданным числом листьев – число Каталана. На рисунке представлены пять деревьев с 4 листьями в каждом.
Такие деревья уже обсуждались на Хабре
- Любые деревья. Число неизоморфных деревьев с заданным числом вершин также равно числу Каталана. Такие деревья тоже обсуждались
- Монотонные пути в квадрате – маршруты из левого нижнего угла квадрата в правый верхний, которые идут по линиям сетки вверх или вправо и не заходят выше диагонали. На рисунке все такие пути для квадрата 3x3.
- Триангуляции многоугольника. Количество различных триангуляций выпуклого многоугольника диагоналями равно числу Каталана.
- Разбиение вершин многоугольника на пары. Четное число точек на окружности можно объединить в пары непересекающимися хордами. Число способов таких объединений также равно числу Каталана.
- Таблица Юнга – прямоугольник, заполненный последовательными числами так, чтобы они возрастали во всех строках и столбцах. Число таблиц Юнга размером 2xn также выражается числом Каталана.
Для каждой из этих конструкций можно либо по индукции, либо реккурентными соотношен��ями доказать, что число соответствующих объектов выражается числом Каталана. Не буду останавливаться на этих доказательствах – их можно найти в учебниках по дискретной математике. Также есть некоторые замечательные соотношения, которые можно получить, используя некоторые из упомянутых построений. Но это требует написания громоздких формул, чего хотелось бы избежать. Сейчас интереснее другое – неужели совпадение всех этих количеств для совершенно разных вещей случайность?
Конечно же, нет. Связь этих конструкций гораздо глубже. Можно построить взаимнооднозначное соответствие между этими объектами и некоторые из таких соответствий я попробую продемонстрировать. Помимо простого любопытства это имеет и некоторую практическую ценность. Например, задачу о генерации всех бинарных деревьев (решение которой в лоб неочевидно) можно свести к гораздо более простой задаче о генерации скобочных последовательностей.
Соответствие 1
Очень легко построить соответствие между скобочными последовательностями и монотонными путями в квадрате. Читая скобочную последовательность слева направо, будем строить путь, начав из левого нижнего угла, – для каждой открывающейся скобки нарисуем горизонтальный отрезок, для закрывающейся скобки – вертикальный.
Так как в последовательности было равное число открывающихся и закрывающихся скобок, то путь в итоге закончится в правом верхнем углу, а тот факт, что каждая открывающаяся скобка стоит раньше соответствующей ей закрывающейся скобки (ведь последовательность — правильная) гарантирует нам, ч��о путь не перейдет в верхнюю половину квадрата. Очевидно, что это построение обратимо и из каждого монотонного пути можно получить скобочную последовательность.
На приведенном рисунке соответствующие скобки и отрезки отмечены одним цветом. Хорошо заметно, что отрезки, соответствующие одной паре скобок «видят друг друга»:
Соответствие 2
В качестве второй задачи построим соответствие между правильными скобочными последовательностями и таблицами Юнгам 2xn. Тут тоже все просто. Пронумеруем скобки слева направо. Если скобка открывающаяся, то соответствующее ей число пишем в верхнюю строку. Если закрывающаяся, то в – нижнюю. Так как i-ая открывающаяся скобка всегда стоит левее i-ой закрывающейся, то число соответствующее открывающейся скобке будет меньше числа, соответствующего закрывающей. А значит, верхнее число в таблице окажется меньше нижнего в той же колонке, то есть из правильной скобочной последовательности мы получили таблицу Юнга. Это построение также обратимо, а значит получено взаимно-однозначное соответствие.
Соответствие 3
Теперь займемся бинарными деревьями. Очень легко увидеть соответствие между бинарными деревьями и расстановками скобок в выражении с однородными операциями, но это дает несколько другие последовательности. Для привязки бинарных деревьев к правильным скобочным последовательностям надо воспользоваться несколько другим подходом. Воспользуемся стандартным обходом дерева и пронумеруем вершины (корень примем за 0) в порядке обхода. Теперь, если при переходе к числу I мы спустились от родителя к ребенку, то на i-ое место ставим открывающуюся скобку. В противном случае ставим закрывающуюся.
Дерево – бинарное, поэтому у каждого узла есть сосед. А значит, спустившись к ребенку и поставив открывающуюся скобку, мы рано или поздно доберемся до его соседа и поставим закрывающуюся скобку. Это гарантирует правильность получившейся последовательности. Построение легко обратить и взяв за основу скобочную последовательность получить бинарное дерево.
Заметим, что если в скобочной последовательности n пар то соответствующее дерево имеет n+1 лист.
Соответствие 4
Для построени�� соответствия между триангуляциями многоугольника проще всего использовать бинарное дерево. На этот раз мы занумеруем в нем все листья слева направо (остальные узлы пометим буквами). Для триангуляции возьмем многоугольник, в котором вершин на одну больше, чем листьев в дереве. Одну из сторон этого многоугольника отметим, как стартовую, а остальные занумеруем (для наглядности – против часовой стрелки).
Далее выполняем следующую процедуру – если две вершины дерева соседние, то соответствующие стороны многоугольника «стянем» диагональю, которую пометим той буквой, которой помечен родитель этой пары узлов в дереве. Далее продолжаем процедуру «стягивания» пока от многоугольника не останется единственный стартовый отрезок.
Как можно заметить три стороны каждого треугольника в получившемся разбиении соответствуют одному родительскому узлу и двум его потомкам. Поэтому, если взять два разных дерева, то получится два разных разбиения.
Вместо эпилога
Ну и в заключение приведу табличку, в котором изображено соответствие объектов для третьего числа Каталана.
