!!§!! Вспомогательный пункт к пунктам ((:gruppe#бинарная_операция БИНАРНАЯ ОПЕРАЦИЯ)) и ((:codes#префиксные_древовидные_коды ПРЕФИКСНЫЕ КОДЫ)) ---- ==Числа Каталана== ~~TOC~~ **Задача.** Пусть $ \ast $ означает ((:gruppe#бинарная_операция бинарную операцию)) на множестве $ \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 $? Оказывается, последовательность выполнения операций удобно изобразить схематично в виде дерева. Так, на рисунке {{ gruppe:tree_mult.jpg |}} указаны $ 5_{} $ всех возможных вариантов расстановки скобок при вычислении выражения $ A \ast B \ast C \ast D $. Поставил исходную задачу и "деревообработал" ее ((:biogr#кэли Кэли)) в XIX веке. Итак, каждое дерево имеет ровно один корень и $ n_{} $ "листьев", которые принято называть //висячими вершинами//. Корни и "листья" связаны собственно деревом, вид которого ограничивается единственным условием: из каждой точки ветвления (они также называются вершинами, только //невисячими//) должно выходить ровно по две ветки (таким образом количество таких точек ветвления равно $ n_{}-1 $). Итак, поставленная выше задача переформулируется в ей эквивалентную --- **Задача.** Сколько существует деревьев с указанными свойствами? Следующий результат дает ответ на оба вопроса; мы сформулируем его в терминах первоначальной задачи. !!Т!! **Теорема [Каталан].**[[**Каталан Эжен** Шарль (Catalan Eugène Charles, 1814-1894) --- бельгийский математик. Биография ☞ ((http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Catalan.html ЗДЕСЬ)).]] //Максимальное количество значений выражения// $ {\mathfrak a}_1 \ast {\mathfrak a}_2 \ast \dots \ast {\mathfrak a}_n $ //в зависимости от расстановок в нем скобок равно // **((http://en.wikipedia.org/wiki/Catalan_number (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} $ означает //((:algebra2:notations#биномиальный_коэффициент биномиальный коэффициент)), а// $ (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_{} $. В результате, путь, ведущий из корня до каждой висячей вершины, оказывается закодированным. {{ gruppe:tree_mult1.jpg |}} Расставив в вершинах буквы (символы), которые нужно закодировать, получим их выражения в виде двоичных последовательностей --- //кодовых слов//. Разным деревьям соответствуют разные коды. Все они обладают свойством, которое называется //префиксностью// (см. ☞ ((:codes#префиксные_древовидные_коды ЗДЕСЬ)) ). Теорема Каталана дает ответ на следующий вопрос: **Задача.** Сколько существует ((:codes#префиксные_древовидные_коды примитивных префиксных кодов)), состоящих из $ n_{} $ кодовых слов? Число из теоремы не учитывает возможности перестановки кодируемых символов (букв) для каждого набора кодовых слов. ==Задача Эйлера о триангуляции многоугольника== **Задача.** Сколькими способами можно разделить выпуклый многоугольник на треугольники его непересекающимися диагоналями? Обозначим $ P_n $ --- число всевозможых разбиений на треугольники произвольного выпуклого $ n $-угольника. !!П!! **Пример.** $ P_3=1,P_4=2,P_5=5, P_6=14, \dots $ {{ gruppe:triang_zat.png |}} !!Т!! **Теорема.** $ 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