Задача. Пусть $ \ast $ означает бинарную операцию на множестве $ \mathbb S_{} $, и $ \{ {\mathfrak a}_1, {\mathfrak a}_2, \dots, {\mathfrak a}_n \} \subset \mathbb S_{} $. Сколько различных значений (в зависимости от расстановок скобок) может принимать выражение $ {\mathfrak a}_1 \ast {\mathfrak a}_2 \ast \dots \ast {\mathfrak a}_n $?

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

указаны $ 5_{} $ всех возможных вариантов расстановки скобок при вычислении выражения $ A \ast B \ast C \ast D $. Поставил исходную задачу и «деревообработал» ее Кэли в XIX веке. Итак, каждое дерево имеет ровно один корень и $ n_{} $ «листьев», которые принято называть висячими вершинами. Корни и «листья» связаны собственно деревом, вид которого ограничивается единственным условием: из каждой точки ветвления (они также называются вершинами, только невисячими) должно выходить ровно по две ветки (таким образом количество таких точек ветвления равно $ n_{}-1 $). Итак, поставленная выше задача переформулируется в ей эквивалентную —

Задача. Сколько существует деревьев с указанными свойствами?

Следующий результат дает ответ на оба вопроса; мы сформулируем его в терминах первоначальной задачи.

Теорема [Каталан].¹⁾ Максимальное количество значений выражения $ {\mathfrak a}_1 \ast {\mathfrak a}_2 \ast \dots \ast {\mathfrak a}_n $ в зависимости от расстановок в нем скобок равно (n-1)-му числу Каталана²⁾

$$C_{n-1}=\frac{1}{n} C_{2n-2}^{n-1}=C_{2n-2}^{n-1}-C_{2n-2}^{n}=\frac{(2n-3)!!}{n!} 2^{n-1} \ . $$ Здесь $ C_{N}^{M} $ означает биномиальный коэффициент, а $ (2n-3)!! $ — произведение всех нечетных чисел от $ 1_{} $ до $ 2n-3 $.

Пример.

Числа Каталана подчиняются следующему рекуррентному соотношению:

$$ C_n=C_0C_{n-1}+C_1C_{n-2}+\dots + C_{j}C_{n-1-j}+ \dots +C_{n-1}C_0 \quad npu \quad C_0=1, C_1=1 . $$

Укажем еще одно применение деревьев — уже относящееся к XX веку. Пронумеруем ветви дерева: каждой правой ветви, идущей из невисячей вершины, поставим в соответствие $ 1_{} $, каждой левой — $ 0_{} $. В результате, путь, ведущий из корня до каждой висячей вершины, оказывается закодированным.

Расставив в вершинах буквы (символы), которые нужно закодировать, получим их выражения в виде двоичных последовательностей — кодовых слов. Разным деревьям соответствуют разные коды. Все они обладают свойством, которое называется префиксностью (см. ☞ ЗДЕСЬ ). Теорема Каталана дает ответ на следующий вопрос:

Задача. Сколько существует примитивных префиксных кодов, состоящих из $ n_{} $ кодовых слов?

Задача. Сколькими способами можно разделить выпуклый многоугольник на треугольники его непересекающимися диагоналями?

Обозначим $ P_n $ — число всевозможых разбиений на треугольники произвольного выпуклого $ n $-угольника.

Пример. $ P_3=1,P_4=2,P_5=5, P_6=14, \dots $

Теорема. $ P_n=C_{n-2} $.

Доказательство [Бине]. Пусть $ M= A_1A_2\dots A_{n+1} $ — выпуклый $ (n+1) $-угольник. В каждом разложении многоугольника $ M $ сторона $ A_1A_2 $ является основанием треугольника, третьей вершиной которого может быть любая из точек $ A_3,\dots, A_{n+1} $.

• Треугольнику $ A_1A_2A_3 $ соответствует число триангуляций, равное $ P_n $,
• треугольнику $ A_1A_2A_4 $ — число, равное $ P_{n-1}P_3 $,
• треугольнику $ A_1A_2A_5 $ — число, равное $ P_{n-2}P_4 $,

и т.д. Все эти разбиения различны и их число равно $ P_{n+1} $: $$P_{n+1}=P_n+P_3P_{n-1}+P_4P_{n-2}+\dots+P_{n-1}P_3 +P_n\, . $$ ♦

[1]. Реньи А. Трилогия о математике. М.Мир.1980.

[2]. Бертранъ Ж. Дифференцiальное исчисленiе. СПб. Изд-во «Наука и жизнь», 1911