TECHNOLOGY - познавательный журнал

Technology - Познавательный Журнал
13 мая 2015

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

Несомненно, самым замечательным математическим фактом является тождество e^пi=-1. В нем удивительным образом сошлись, казалось бы, совершенно не связанные константы из разных областей математики. Доказать это тождество не так сложно, но объяснить его, понять глубинный смысл, удается немногим. В качестве еще одного замечательного факта хотелось бы вспомнить числа Каталана, которые удивительным образом всплывают в самых разных комбинаторных задачах.

Само число Каталана выражается формулой C(n) = (2n)!/n!(n 1)!, где восклицательный знак, как обычно, обозначает факториал. Начало последовательности выглядит так: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…

Англоязычная «Википедия» утверждает, что известно, как минимум 66 различных конструкций, которые приводят к появлению чисел Каталана. Вот некоторые из них:

1. Правильные скобочные последовательности — наборы открывающихся и закрывающихся скобок, в которых каждой открывающейся скобке соответствует закрывающаяся. Число возможных последовательностей с фиксированным числом пар скобок выражается числом Каталана. Например, 14 правильных последовательностей из четырех пар скобок:
(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(),
(())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()

2. Двоичные деревья — деревья, из каждого узла которых (кроме листьев) выходит ровно две ветки. Количество бинарных деревьев с заданным числом листьев — число Каталана.

3. Любые деревья. Число неизоморфных деревьев с заданным числом вершин также равно числу Каталана.

4. Монотонные пути в квадрате — маршруты из левого нижнего угла квадрата в правый верхний, которые идут по линиям сетки вверх или вправо и не заходят выше диагонали.

5. Триангуляции многоугольника. Количество различных триангуляций выпуклого многоугольника диагоналями равно числу Каталана.

6. Разбиение вершин многоугольника на пары. Четное число точек на окружности можно объединить в пары непересекающимися хордами. Число способов таких объединений также равно числу Каталана.

7. Таблица Юнга — прямоугольник, заполненный последовательными числами так, чтобы они возрастали во всех строках и столбцах. Число таблиц Юнга размером 2xn также выражается числом Каталана.