Математика. Числа Каталана.

Числа Каталана — числовая последовательность, встречающаяся в удивительном числе комбинаторных задач. Эта последовательность названа в честь бельгийского математика Каталана (Catalan), жившего в 19 веке, хотя на самом деле она была известна ещё Эйлеру (Euler), жившему за век до Каталана.

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

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

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

Первым с числами Каталана столкнулся Леонард Эйлер. Он подсчитал, сколькими способами выпуклый многоугольник может быть разделён на треугольники непересекающимися диагоналями.

В качестве примера можно привести способы разбиения на треугольники следующих фигур: квадрата, пятиугольника и шестиугольника.

Заметим, что в каждом из случаев¸ независимо от количества сторон n- угольника, число диагоналей равно (n – 3), а число треугольников (n – 2).

Число различных комбинаций указанного вида для каждого из многоугольников есть первые четыре члена (если начинать с треугольника) последовательности Каталана.

1 2 5 14

и т. д.

Эйлер, используя метод математической индукции, который, по его словам, здесь оказался трудоёмким, получил такую формулу:

Очень простые рекуррентные формулы получаются, если поместить в начале последовательности ещё одну единицу.

Пусть k – последнее вычисленное число Каталана, а n – номер следующего числа.

Тогда это число вычисляется по формуле:  .

Современник Эйлера, Иоганн Андрес фон Сегнер, получил загадочную рекуррентную формулу для последовательности Каталана вида: 1; 1; 2; 5; …

Запишем в ряд все уже найденные числа Каталана, а под ними запишем те же числа в обратном порядке. Умножим каждое верхнее число на соответствующее нижнее и сложим получившиеся произведения; результат и будет следующим числом Каталана.

1 1 2 5 14

*

14 5 2 1 1

14 + 5 + 4 +5 +14 = 42

Теперь вернёмся к задаче о разбиении многоугольников. Эта задача изоморфна и задачам, казалось бы с ней. Эта задача изоморфна и задачам, казалось бы с ней не связанным.

Сам Ижен Шарль Каталан, бельгийский математик, в 1838 г. решил следующую задачу: «Пусть имеется цепочка из nбукв, расположенных в заданном порядке. Необходимо расставить (n – 1) пару скобок так, чтобы внутри каждой пары стояло ровно два «выражения». Этими спаренными выражениями могут быть либо две соседние буквы, либо два соседних выражения. Сколькими способами могут быть поставлены скобки?»

Для букв a и b имеется только одна возможность: (ab).

Для трёх букв таких возможностей две: ((ab) c) (a (bc)).

Для четырёх букв количество способов увеличится до пяти:

((ab)(cd)) (((ab) c) d) (a (bc) d) ((a (bc) d).

Эти числа 1; 2; 5 – первые числа Каталана, оказывается, числа Каталана дают нам количество способов расстановки скобок в буквенных цепочках соответствующих длин.

В 1961 г. Фордер, описывая числа Каталана, указал простой способ взятого однозначного соответствия между подсчётом комбинаций в многоугольниках и расстановкой скобок в буквенных цепочках.

Рассмотрим, например, семиугольник:

Обозначение основания идёт последним и обозначение для него однозначно определяется триангуляцией («триангуляция» - разбиение на треугольники). Если применить указанный приём для выше перечисленных многоугольников, то получим цепочки букв с расставленными скобками.

Английский математик Артур Кэли доказал, что числа Каталана перечисляют все плоские корневые кубические деревья (именно, n – е число Каталана равно количеству плоских корневых кубических деревьев с (n + 1) - ой концевой вершиной).

Дерево – это связный граф (вершины, соединённые отрезками), не имеющий циклов.

«Плоский» означает, что граф нарисован на плоскости без пересечений.

«Корневое» - это дерево имеет ствол, конец которого имеет корень.

Таким образом, граф можно нарисовать в виде как бы растущего вверх из земли дерева.

«Кубическое» означает, что в каждой вершине (кроме корня и концов веток) дерево разветвляется, образуя точки, в которых встречаются три ребра.

Под каждой цепочкой букв со скобками записано двоичное число, получаемое заменой всех скобок «1», а всех букв – «0», пропуская правые скобки. Для правых скобок нет необходимости вводить обозначение, т. к. заданное положение левых скобок и метод группировки букв определяет постановку скобок единственным образом.

Рассмотрим ещё такую задачу:

«Возьмём шахматные доски со сторонами 2; 3; 4; …, в которых закрашены все квадраты северо-западнее главной диагонали. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно, не заходя при этом на закрашенные клетки. Сколько существует путей ладьи на доске со стороной а?»

Решение:

Под стороной длины nнапишем двоичное число, соответствующее корневому дереву (кубическому) с nконцевыми вершинами.

Продвигаясь по двоичным разрядам числа слева на право будем двигать ладью вправо, проходя «1», и вверх, проходя «0» (последняя двоичная цифра не учитывается). Эта последовательность двоичных цифр определяет путь, и все пути ладьи могут быть получены таким образом.