УказательРазделыОбозначенияАвторО проекте


§

Вспомогательный пункт к пунктам БИНАРНАЯ ОПЕРАЦИЯ и ПРЕФИКСНЫЕ КОДЫ


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

Задача. Пусть \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). Итак, поставленная выше задача переформулируется в ей эквивалентную —

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

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

Т

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

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.

П

Пример.

n 3 4 5 6 7 8 9 10
число Каталана C_{n-1} 2 5 14 42 132 429 1430 4862

=>

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

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

1) Каталан Эжен Шарль (Catalan Eugène Charles, 1814-1894) — бельгийский математик. Биография ЗДЕСЬ.
2) Хотя, по-видимому, эти числа были известны Эйлеру.

2018/12/06 21:02 редактировал au