Каталонский номер

Рекурсивная целочисленная последовательность

C ₅ = 42 непересекающихся раздела набора из 5 элементов (ниже остальные 10 из 52 разделов )

В комбинаторной математике каталонские числа представляют собой последовательность натуральных чисел , которые встречаются в различных задачах счета , часто с участием рекурсивно определенных объектов. Они названы в честь французско-бельгийского математика Эжена Шарля Каталана .

n -е число Каталана может быть выражено непосредственно через центральные биномиальные коэффициенты :

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\qquad {\text{for }}n\geq 0.}$

Первые каталонские числа для n = 0, 1, 2, 3,... :

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ... (последовательность A000108 в OEIS ).

Характеристики

Альтернативное выражение для C _n :

${\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}}$для ${\displaystyle n\geq 0,}$

что эквивалентно приведенному выше выражению, поскольку . Это выражение показывает, что C _n — целое число , что не сразу очевидно из первой приведенной формулы. Это выражение составляет основу доказательства правильности формулы. ${\displaystyle {\tbinom {2n}{n+1}}={\tfrac {n}{n+1}}{\tbinom {2n}{n}}}$

Другое альтернативное выражение:

${\displaystyle C_{n}={\frac {1}{2n+1}}{2n+1 \choose n}\,,}$

что можно непосредственно интерпретировать в терминах леммы о цикле ; см. ниже.

Каталонские числа удовлетворяют рекуррентным соотношениям

${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n}=\sum _{i=1}^{n}C_{i-1}C_{n-i}\quad {\text{for }}n>0}$

и

${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}\quad {\text{for }}n>0.}$

Асимптотически каталонские числа растут как

$${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}},}$$

nn

Это можно доказать, используя асимптотический рост центральных биномиальных коэффициентов , аппроксимацию Стирлинга для или через производящие функции . ${\displaystyle n!}$

^{Более точный асимптотический анализ показывает , что} числа Каталана аппроксимируются приближением четвертого порядка ^.

${\displaystyle C_{n}\sim {\frac {4^{n-5}(8n(16n(8n-9)+145)-1155)}{{\sqrt {\pi }}n^{9/2}}}}$.

Нечетными каталонскими числами C _n являются только те, для которых n = 2 ^k − 1 ; все остальные четные. Единственными простыми каталонскими числами являются C ₂ = 2 и C ₃ = 5 . ^[1]

Каталанские числа имеют целочисленные представления ^{[2] [3]}

${\displaystyle C_{n}={\frac {1}{2\pi }}\int _{0}^{4}x^{n}{\sqrt {\frac {4-x}{x}}}\,dx\,={\frac {2}{\pi }}4^{n}\int _{-1}^{1}t^{2n}{\sqrt {1-t^{2}}}\,dt.}$

что сразу дает . ${\displaystyle \sum _{n=0}^{\infty }{\frac {C_{n}}{4^{n}}}=2}$

Это имеет простую вероятностную интерпретацию. Рассмотрим случайное блуждание по целочисленной строке, начиная с 0. Пусть -1 будет состоянием «ловушки», так что если ходок достигнет -1, он останется там. Ходок может прийти в состояние ловушки в моменты времени 1, 3, 5, 7..., и число способов, которыми он может прийти в состояние ловушки за раз, равно . Поскольку одномерное случайное блуждание является рекуррентным, вероятность того, что ходок в конечном итоге достигнет -1, равна . ${\displaystyle 2k+1}$ ${\displaystyle C_{k}}$ ${\displaystyle \sum _{n=0}^{\infty }{\frac {C_{n}}{2^{2n+1}}}=1}$

Приложения в комбинаторике

В комбинаторике существует множество задач о счете , решение которых дают числа Каталана. Книга комбинаториста Ричарда П. Стэнли «Перечислительная комбинаторика: Том 2» содержит набор упражнений, которые описывают 66 различных интерпретаций каталонских чисел. Ниже приведены несколько примеров с иллюстрациями случаев C ₃ = 5 и C ₄ = 14 .

Решетка из 14 слов Дейка длиной 8 – ( и ) , интерпретируемых как вверх и вниз.

• C _n — количество слов Дика ^[4] длины 2 n . Слово Дайка — это строка , состоящая из n X и n Y, такая, что ни в одном начальном сегменте строки Y не превышает количество X. Например, ниже приведены слова Дика длиной до 6:

XY

XXYY XYXY

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

• Переинтерпретируя символ X как открывающую скобку и Y как закрывающую скобку, C _n подсчитывает количество выражений, содержащих n пар скобок, которые правильно сопоставлены:

((())) (()()) (())() ()(()) ()()()

• C _n — это количество различных способов, которыми n  + 1 фактор может быть полностью заключен в круглые скобки (или количество способов связать n применений бинарного оператора , как в задаче умножения цепочки матриц ). Например, для n = 3 у нас есть следующие пять различных заключений четырех факторов в круглые скобки:

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

• Последовательные применения бинарного оператора можно представить в виде полного двоичного дерева , пометив каждый лист a,b,c,d . Отсюда следует, что C _n — это количество полных бинарных деревьев с n  + 1 листьями или, что то же самое, с n внутренними узлами:

Ассоциэдр 4- го порядка с C ₄ =14 полными бинарными деревьями с 5 листьями

• C _n — количество неизоморфных упорядоченных (или плоских) деревьев с n + 1 вершиной. ^[5] См. кодирование общих деревьев как двоичных деревьев . Например, C _n — это количество возможных деревьев синтаксического анализа предложения (при условии двоичного ветвления) при обработке естественного языка.
• C _n — количество монотонных путей решетки по краям сетки с n × n квадратными ячейками, не выходящим за пределы диагонали. Монотонный путь — это путь, который начинается в левом нижнем углу, заканчивается в правом верхнем углу и полностью состоит из ребер, направленных вправо или вверх. Подсчет таких путей эквивалентен подсчету слов Дика: X означает «движение вправо», а Y означает «движение вверх».

На следующих диаграммах показан случай n = 4:

Это можно представить, перечислив каталонские элементы по высоте столбца: ^[6]

Темный треугольник — это корневой узел, светлые треугольники соответствуют внутренним узлам бинарных деревьев, а зеленые полосы — листьям.

[0,0,0,0] [0,0,0,1] [0,0,0,2] [0,0,1,1]

[0,1,1,1] [0,0,1,2] [0,0,0,3] [0,1,1,2] [0,0,2,2] [0,0, 1,3]

[0,0,2,3] [0,1,1,3] [0,1,2,2] [0,1,2,3]

• Выпуклый многоугольник с n +  2 сторонами можно разрезать на треугольники , соединяя вершины непересекающимися отрезками линий (разновидность триангуляции многоугольника ). Число образованных треугольников равно n , а количество различных способов, которыми это можно сделать, равно C _n . Следующие шестиугольники иллюстрируют случай n = 4:

• C _n — количество сортируемых по стеку перестановок {1, ..., n }. Перестановка w называется сортируемой стеком , если S ( w ) = (1,...,  n ), где S ( w ) определяется рекурсивно следующим образом: напишите w =  unv , где n — наибольший элемент в w и u , а v — более короткие последовательности, и установите S ( w ) =  S ( u ) S ( v ) n , где S — тождество для одноэлементных последовательностей.
• C _n — количество перестановок {1, ...,  n }, которые избегают шаблона перестановки  123 (или, альтернативно, любого другого шаблона длины 3); то есть количество перестановок без трехчленной возрастающей подпоследовательности. Для n = 3 это 132, 213, 231, 312 и 321. Для n = 4 это 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312. и 4321.
• C _n — количество непересекающихся разбиений множества {1, ...,  n }. Тем более , C _n никогда не превышает n -го числа Белла . C _n — это также количество непересекающихся разделов набора {1, ..., 2 n }, в которых каждый блок имеет размер 2.
• C _n — количество способов замостить ступеньку высоты n n прямоугольниками . Разрезание антидиагонали и просмотр только краев дает полные бинарные деревья. Следующий рисунок иллюстрирует случай n  = 4:

• C _n — это количество способов сформировать «горный хребет» с n движениями вверх и n движениями вниз, которые все остаются выше горизонтальной линии. Интерпретация горного хребта заключается в том, что горы никогда не уйдут за горизонт.

• C _n — количество стандартных таблиц Юнга, диаграмма которых представляет собой прямоугольник размером 2× n . Другими словами, это количество способов, которыми числа 1, 2, ..., 2 n можно расположить в прямоугольнике размером 2 на n так, чтобы каждая строка и каждый столбец увеличивались. Таким образом, формула может быть выведена как частный случай формулы длины крючка .

123 124 125 134 135456 356 346 256 246

• ${\displaystyle C_{n}}$— это количество последовательностей длины n , которые начинаются с , и могут увеличиваться либо на , либо уменьшаться на любое число (по крайней мере до ). Ибо это . По пути Дика начните счетчик с 0 . X увеличивает счетчик на 1 , а Y уменьшает его на 1 . Запишите значения только в точках X. По сравнению с аналогичным представлением чисел Белла отсутствует только . ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle n=4}$ ${\displaystyle 1234,1233,1232,1231,1223,1222,1221,1212,1211,1123,1122,1121,1112,1111}$ ${\displaystyle 1213}$

Доказательство формулы

Есть несколько способов объяснить, почему формула

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}}$

решает комбинаторные задачи, перечисленные выше. Первое доказательство ниже использует производящую функцию . Остальные доказательства являются примерами биективных доказательств ; они включают в себя буквально подсчет совокупности каких-то объектов, чтобы прийти к правильной формуле.

Первое доказательство

Прежде всего заметим, что все перечисленные выше комбинаторные задачи удовлетворяют рекуррентному соотношению Сегнера ^[7]

${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0.}$

Например, каждое слово Дика w длины ≥ 2 можно единственным образом записать в виде

ш = Х ш ₁ Y ш ₂

с (возможно, пустыми) словами Дика w ₁ и w ₂ .

Производящая функция каталонских чисел определяется формулой

${\displaystyle c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}.}$

Приведенное выше рекуррентное соотношение затем можно резюмировать в виде производящей функции соотношением

${\displaystyle c(x)=1+xc(x)^{2};}$

другими словами, это уравнение следует из рекуррентного соотношения путем разложения обеих частей в степенные ряды . С одной стороны, рекуррентное соотношение однозначно определяет числа Каталана; с другой стороны, интерпретируя xc ² − c + 1 = 0 как квадратное уравнение для c и используя квадратичную формулу , соотношение производящей функции можно алгебраически решить, чтобы получить две возможности решения

${\displaystyle c(x)={\frac {1+{\sqrt {1-4x}}}{2x}}}$  или  . ${\displaystyle c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}}$

Из двух возможностей следует выбрать вторую, поскольку только вторая дает

${\displaystyle C_{0}=\lim _{x\to 0}c(x)=1}$.

Член квадратного корня можно разложить в степенной ряд, используя биномиальный ряд.

$${\displaystyle {\begin{aligned}1-{\sqrt {1-4x}}&=-\sum _{n=1}^{\infty }{\binom {1/2}{n}}(-4x)^{n}=-\sum _{n=1}^{\infty }{\frac {(-1)^{n-1}(2n-3)!!}{2^{n}n!}}(-4x)^{n}\\&=-\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n-1)!!}{2^{n+1}(n+1)!}}(-4x)^{n+1}=\sum _{n=0}^{\infty }{\frac {2^{n+1}(2n-1)!!}{(n+1)!}}x^{n+1}\\&=\sum _{n=0}^{\infty }{\frac {2(2n)!}{(n+1)!n!}}x^{n+1}=\sum _{n=0}^{\infty }{\frac {2}{n+1}}{\binom {2n}{n}}x^{n+1}\,.\end{aligned}}}$$

$${\displaystyle c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}x^{n}\,.}$$

Второе доказательство

Рисунок 1. Недопустимая часть пути (красный пунктир) перевернута (сплошной красный). Плохие пути (после переворота) достигают ( n  – 1,  n  + 1) вместо ( n , n ).

Мы подсчитываем количество путей, которые начинаются и заканчиваются на диагонали сетки n  ×  n . Все такие пути имеют n ступеней вправо и n ступеней вверх. Поскольку мы можем выбирать, какой из 2n шагов является верхним или правым, в целом существует монотонные пути этого типа. Плохой путь пересекает главную диагональ и касается следующей, более высокой диагонали (красный на рисунке) . ${\displaystyle {\tbinom {2n}{n}}}$

Часть пути после более высокой диагонали затем переворачивается вокруг этой диагонали, как показано красной пунктирной линией. Это поменяет местами все правильные шаги на шаги вверх и наоборот. На участке пути, который не отражен, на один шаг вверх больше, чем на шаги вправо, поэтому оставшийся участок плохого пути имеет на один шаг вправо больше, чем шаги вверх. Когда эта часть пути будет отражена, она будет иметь на один шаг вверх больше, чем шаги вправо.

Поскольку шагов по-прежнему 2n , теперь есть n  + 1 шагов вверх и n  − 1 шагов вправо. Таким образом, вместо того, чтобы достичь ( n , n ), все плохие пути после отражения заканчиваются в ( n  − 1,  n  + 1). Поскольку каждый монотонный путь в сетке ( n  − 1) × ( n  + 1) пересекает более высокую диагональ, а процесс отражения обратим, отражение представляет собой биекцию между плохими путями в исходной сетке и монотонными путями в новой. сетка.

Таким образом, количество плохих путей равно:

${\displaystyle {n-1+n+1 \choose n-1}={2n \choose n-1}={2n \choose n+1}}$

а количество каталонских путей (т.е. хороших путей) получается удалением количества плохих путей из общего количества монотонных путей исходной сетки,

${\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}={\frac {1}{n+1}}{2n \choose n}.}$

С точки зрения слов Дика, мы начинаем с (не-Дейка) последовательности из n X и n Y и меняем местами все X и Y после первого Y, который нарушает условие Дика. После этого Y заметьте, что Y ровно на один больше, чем X.

Третье доказательство

Это биективное доказательство дает естественное объяснение слагаемому n  + 1, появляющемуся в знаменателе формулы для  C _n . Обобщенную версию этого доказательства можно найти в статье Рукавицкой Йозефа (2011). ^[8]

Рисунок 2. Путь с превышением 5.

Учитывая монотонный путь, превышение пути определяется как количество вертикальных ребер над диагональю. Например, на рисунке 2 ребра над диагональю отмечены красным, поэтому превышение этого пути равно 5.

Учитывая монотонный путь, превышение которого не равно нулю, мы применяем следующий алгоритм, чтобы построить новый путь, превышение которого на 1 меньше того, с которого мы начали.

• Начиная с левого нижнего угла, следуйте по пути, пока он не пройдет выше диагонали.
• Продолжайте идти по пути, пока он снова не коснется диагонали. Обозначим через X первое достигнутое такое ребро.
• Поменяйте местами часть пути, происходящую до X , на часть, происходящую после X.

На рисунке 3 черная точка указывает точку, где путь впервые пересекает диагональ. Черный край — это X , и мы помещаем последнюю точку решетки красной части в верхний правый угол, а первую точку решетки зеленой части в левый нижний угол и размещаем X соответственно, чтобы создать новый путь. , показанный на второй диаграмме.

Рисунок 3. Зеленая и красная части меняются местами.

Превышение снизилось с 3 до 2 . Фактически, алгоритм заставляет превышение уменьшаться на 1 для любого пути, который мы ему подаем, потому что первый вертикальный шаг, начинающийся по диагонали (в точке, отмеченной черной точкой), является единственным вертикальным ребром, который не находится над диагональ ниже нее, когда мы применяем алгоритм - все остальные вертикальные ребра остаются на той же стороне диагонали.

Рисунок 4. Все монотонные пути в сетке 3×3, иллюстрирующие алгоритм уменьшения превышения.

Можно видеть, что этот процесс обратим : для любого пути P , превышение которого меньше n , существует ровно один путь, который дает P , когда к нему применяется алгоритм. Действительно, (черное) ребро X , которое изначально было первым горизонтальным шагом, заканчивающимся на диагонали, стало последним горизонтальным шагом , начинающимся на диагонали. Альтернативно, измените исходный алгоритм, чтобы найти первое ребро, проходящее ниже диагонали.

Это означает, что количество путей превышения n равно количеству путей превышения n  - 1, которое равно количеству путей превышения n  - 2, и так далее, вплоть до нуля. Другими словами, мы разделили набор всех монотонных путей на n  + 1 класс одинакового размера, что соответствует возможным превышениям между 0 и n . Поскольку существуют монотонные пути, получаем искомую формулу ${\displaystyle \textstyle {2n \choose n}}$ ${\displaystyle \textstyle C_{n}={\frac {1}{n+1}}{2n \choose n}.}$

Рисунок 4 иллюстрирует ситуацию для  n  = 3. Каждый из 20 возможных монотонных путей появляется где-то в таблице. В первом столбце показаны все пути превышения три, которые полностью лежат выше диагонали. Столбцы справа показывают результат последовательных применений алгоритма, при этом превышение уменьшается на единицу за раз. Строок пять, то есть  C ₃  = 5, а в последнем столбце отображаются все пути не выше диагонали.

Используя слова Дайка, начните с последовательности от . Позвольте быть первым X , который приводит начальную подпоследовательность к равенству, и настройте последовательность как . Новая последовательность . ${\displaystyle \textstyle {\binom {2n}{n}}}$ ${\displaystyle X_{d}}$ ${\displaystyle (F)X_{d}(L)}$ ${\displaystyle LXF}$

Четвертое доказательство

В этом доказательстве используется определение триангуляции каталонских чисел, чтобы установить связь между C _n и C _{n +1} .

Дан многоугольник P с n  + 2 сторонами и триангуляцией. Отметьте одну из его сторон как основание, а также сориентируйте одно из 2 n  + 1 его ребер. Таких отмеченных триангуляций для данной базы имеется (4 n  + 2) C _{n .}

Дан многоугольник Q с n  + 3 сторонами и (разной) триангуляцией. Снова отметьте одну из его сторон как основу. Отметьте одну из сторон, кроме базовой стороны (а не внутреннего края треугольника). Таких отмеченных триангуляций для данной базы существует ( n  + 2) C _{n  + 1 .}

Между этими двумя отмеченными триангуляциями существует простая биекция: мы можем либо свернуть треугольник в Q , сторона которого отмечена (двумя способами, и вычесть те два, которые не могут свернуть основание), либо, наоборот, расширить ориентированное ребро в P. к треугольнику и отметьте его новую сторону.

Таким образом

${\displaystyle (4n+2)C_{n}=(n+2)C_{n+1}}$.

Писать ${\displaystyle \textstyle {\frac {4n-2}{n+1}}C_{n-1}=C_{n}.}$

Потому что

${\displaystyle (2n)!=(2n)!!(2n-1)!!=2^{n}n!(2n-1)!!}$

у нас есть

${\displaystyle {\frac {(2n)!}{n!}}=2^{n}(2n-1)!!=(4n-2)!!!!.}$

Применение рекурсии с дает результат. ${\displaystyle C_{0}=1}$

Пятое доказательство

Это доказательство основано на интерпретации каталонских чисел словами Дейка , а также на количестве способов правильно сопоставить n пар скобок. Мы обозначаем правильную строку (возможно, пустую) буквой c и обратную ей буквой c' . Поскольку любой c можно однозначно разложить на , суммирование по возможным длинам сразу дает рекурсивное определение ${\displaystyle C_{n}}$ ${\displaystyle c=(c_{1})c_{2}}$ ${\displaystyle c_{1}}$

${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0}$.

Пусть b — сбалансированная строка длины 2n , т.е. b содержит равное количество и , поэтому . Сбалансированную строку также можно однозначно разложить на или , поэтому ${\displaystyle (}$ ${\displaystyle )}$ ${\displaystyle \textstyle B_{n}={2n \choose n}}$ ${\displaystyle (c)b}$ ${\displaystyle )c'(b}$

${\displaystyle B_{n+1}=2\sum _{i=0}^{n}B_{i}C_{n-i}.}$

Любая неверная (не каталонская) сбалансированная строка начинается с , а оставшаяся строка имеет на единицу больше , поэтому ${\displaystyle c)}$ ${\displaystyle (}$ ${\displaystyle )}$

${\displaystyle B_{n+1}-C_{n+1}=\sum _{i=0}^{n}{2i+1 \choose i}C_{n-i}}$

Также из определений имеем:

${\displaystyle B_{n+1}-C_{n+1}=2\sum _{i=0}^{n}B_{i}C_{n-i}-\sum _{i=0}^{n}C_{i}\,C_{n-i}=\sum _{i=0}^{n}(2B_{i}-C_{i})C_{n-i}.}$

Следовательно, поскольку это верно для всех n ,

${\displaystyle 2B_{i}-C_{i}={\binom {2i+1}{i}}}$

${\displaystyle C_{i}=2B_{i}-{\binom {2i+1}{i}}}$

${\displaystyle C_{i}=2{\binom {2i}{i}}-{\binom {2i+1}{i}}}$

${\displaystyle C_{i}={\frac {1}{i+1}}{\binom {2i}{i}}}$

Шестое доказательство

Это доказательство основано на интерпретации каталонских чисел словами Дейка и использует лемму о цикле Дворецкого и Моцкина. ^{[9] [10]}

Последовательность X и Y назовем доминирующей , если при чтении слева направо число X всегда строго больше числа Y. Лемма о цикле ^[11] утверждает, что любая последовательность X и Y, где , имеет точно доминирующие круговые сдвиги . Чтобы убедиться в этом, расположите заданную последовательность X и Y по кругу. Повторное удаление пар XY оставляет ровно X. Каждый из этих крестиков был началом доминирующего кругового сдвига, прежде чем что-либо было удалено. Например, рассмотрим . Эта последовательность является доминирующей, но ни один из ее круговых сдвигов , , и не является. ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m>n}$ ${\displaystyle m-n}$ ${\displaystyle m+n}$ ${\displaystyle m-n}$ ${\displaystyle {\mathit {XXYXY}}}$ ${\displaystyle {\mathit {XYXYX}}}$ ${\displaystyle {\mathit {YXYXX}}}$ ${\displaystyle {\mathit {XYXXY}}}$ ${\displaystyle {\mathit {YXXYX}}}$

Строка является словом Дайка, состоящим из X и Y, тогда и только тогда, когда добавление X к слову Дайка дает доминирующую последовательность с X и Y, поэтому мы можем посчитать первое, вместо этого посчитав второе. В частности, при , имеется ровно один доминирующий круговой сдвиг. Существуют последовательности, в которых ровно X и Y. Для каждого из них доминирует только один из круговых сдвигов. Следовательно, существуют различные доминирующие последовательности X и Y, каждая из которых соответствует ровно одному слову Дика. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle m=n+1}$ ${\displaystyle \textstyle {2n+1 \choose n}}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle 2n+1}$ ${\displaystyle \textstyle {\frac {1}{2n+1}}{2n+1 \choose n}=C_{n}}$ ${\displaystyle n+1}$ ${\displaystyle n}$

Матрица Ханкеля

Матрица Ханкеля размера n × n , элементом ( i ,  j ) которого является каталонское число C _{i + j −2,} имеет определитель 1, независимо от значения n . Например, для n = 4 имеем

${\displaystyle \det {\begin{bmatrix}1&1&2&5\\1&2&5&14\\2&5&14&42\\5&14&42&132\end{bmatrix}}=1.}$

Более того, если индексация «сдвинута» так, что запись ( i , j ) заполнена каталонским числом C _{i + j −1} , тогда определитель по-прежнему равен 1, независимо от значения n . Например, для n = 4 имеем

${\displaystyle \det {\begin{bmatrix}1&2&5&14\\2&5&14&42\\5&14&42&132\\14&42&132&429\end{bmatrix}}=1.}$

В совокупности эти два условия однозначно определяют каталонские числа.

Еще одна особенность, уникальная для матрицы Каталана – Ханкеля, заключается в том, что подматрица размера n × n , начинающаяся с 2, имеет определитель n  + 1.

${\displaystyle \det {\begin{bmatrix}2\end{bmatrix}}=2}$

${\displaystyle \det {\begin{bmatrix}2&5\\5&14\end{bmatrix}}=3}$

${\displaystyle \det {\begin{bmatrix}2&5&14\\5&14&42\\14&42&132\end{bmatrix}}=4}$

${\displaystyle \det {\begin{bmatrix}2&5&14&42\\5&14&42&132\\14&42&132&429\\42&132&429&1430\end{bmatrix}}=5}$

и так далее.

История

Каталонские числа в книге Минганту « Быстрый метод получения точного отношения деления круга», том III

Каталонская последовательность была описана в XVIII веке Леонардом Эйлером , которого интересовало количество различных способов деления многоугольника на треугольники. Последовательность названа в честь Эжена Шарля Каталана , который обнаружил связь с выражениями в скобках во время исследования загадки Ханойских башен . Трюк подсчета отражений (второе доказательство) для слов Дейка был найден Дезире Андре в 1887 году.

Название «каталонские числа» произошло от Джона Риордана . ^[12]

В 1988 году выяснилось, что каталонская числовая последовательность использовалась в Китае монгольским математиком Минганту к 1730 году. ^{[13] [14]} Именно тогда он начал писать свою книгу «Гэ Юань Ми Лу Цзе Фа » («Быстрый метод»). для получения точного отношения деления круга] , который был завершен его учеником Чэнь Цзисинь в 1774 году, но опубликован шестьдесят лет спустя. Питер Дж. Ларкомб (1999) обрисовал некоторые особенности творчества Минганту, в том числе стимул Пьера Жарту, который привез в Китай три бесконечные серии в начале 1700-х годов.

Например, Минг использовал каталонскую последовательность для выражения разложения ряда и через . ${\displaystyle \sin(2\alpha )}$ ${\displaystyle \sin(4\alpha )}$ ${\displaystyle \sin(\alpha )}$

Обобщения

Каталонские числа можно интерпретировать как частный случай теоремы Бертрана о голосовании . В частности, это количество способов, которыми кандидат A с n+1 голосами может опередить кандидата B с n голосами. ${\displaystyle C_{n}}$

Двухпараметрическая последовательность неотрицательных целых чисел является обобщением каталонских чисел. По словам Иры Гессель , это так называемые суперкаталонские числа . Их не следует путать с числами Шредера – Гиппарха , которые иногда также называют суперкаталонскими числами. ${\displaystyle {\frac {(2m)!(2n)!}{(m+n)!m!n!}}}$

Для это всего лишь в два раза больше обычных каталонских чисел, а для числа имеют простое комбинаторное описание. Однако другие комбинаторные описания известны только ^[15] для и , ^[16] и найти общую комбинаторную интерпретацию остается открытой проблемой. ${\displaystyle m=1}$ ${\displaystyle m=n}$ ${\displaystyle m=2,3}$ ${\displaystyle 4}$

Сергей Фомин и Натан Ридинг дали обобщенное число Каталана, связанное с любой конечной кристаллографической группой Кокстера , а именно количество полностью коммутативных элементов группы; с точки зрения связанной корневой системы это количество антицепей (или идеалов порядка) в частично упорядоченном множестве положительных корней. Классическое каталонское число соответствует корневой системе типа . Классическое рекуррентное соотношение обобщает: число Каталана диаграммы Кокстера равно сумме чисел Каталана всех ее максимальных собственных поддиаграмм. ^[17] ${\displaystyle C_{n}}$ ${\displaystyle A_{n}}$

Числа Каталана являются решением проблемы моментов Хаусдорфа . ^[18]

Каталонская k -кратная свертка

Каталонская k -кратная свертка, где k=m , выглядит так: ^[19]

${\displaystyle \sum _{i_{1}+\cdots +i_{m}=n \atop i_{1},\ldots ,i_{m}\geq 0}C_{i_{1}}\cdots C_{i_{m}}={\begin{cases}{\dfrac {m(n+1)(n+2)\cdots (n+m/2-1)}{2(n+m/2+2)(n+m/2+3)\cdots (n+m)}}C_{n+m/2},&m{\text{ even,}}\\[5pt]{\dfrac {m(n+1)(n+2)\cdots (n+(m-1)/2)}{(n+(m+3)/2)(n+(m+3)/2+1)\cdots (n+m)}}C_{n+(m-1)/2},&m{\text{ odd.}}\end{cases}}}$

Смотрите также

• Математический портал

• Ассоциэдр
• Теорема Бертрана о голосовании
• Биномиальное преобразование
• Каталонский треугольник
• Каталонское число – Мерсенна
• Фусс – каталонский номер
• Список факториальных и биномиальных тем
• числа Лобба
• Число Моцкина
• Число Нараяны
• Полиномы Нараяны
• Число Шредера – Гиппарха
• Полузаказ
• Решетка Тамари
• Число Уэддерберна – Этерингтона
• Закон полукруга Вигнера

Примечания

1. Коши, Томас; Салмасси, Мохаммед (2006). «Четность и простота каталонских чисел» (PDF) . Математический журнал колледжа . 37 (1): 52–53. дои : 10.2307/27646275. JSTOR  27646275.
2. Чой, Хаёнг; Да, Ён-Нан; Ю, Сонгук (2020), «Каталонские числовые последовательности и последовательности моментов Хаусдорфа», Discrete Mathematics , 343 (5): 111808, 11, arXiv : 1809.07523 , doi : 10.1016/j.disc.2019.111808, MR  4052255, S2CID  2 14165563, Пример 3.1
3. Фэн, Ци; Бай-Ни, Го (2017), «Интегральные представления каталонских чисел и их приложения», Mathematics , 5 (3): 40, doi : 10.3390/math5030040,Теорема 1
4. Пути Дика
5. Стэнли, стр. 221, пример (д)
6. Черпиншек, Матей; Мерник, Лука (2009). «Эффективное представление для решения проблем, связанных с каталонскими числами» (PDF) . Международный журнал чистой и прикладной математики . 56 (4): 589–604.
7. А. де Сегнер, Enumeratio modorum, quibus figurae planae Rectilineae по диагоналям разделенных в треугольнике. Novi commentarii academiae scientiarum Petropolitanae 7 (1758/59) 203–209.
8. Рукавицка Йозеф (2011), Об обобщенных путях Дика, Электронный журнал комбинаторики онлайн
9. Дершовиц, Нахум; Закс, Шмуэль (1980), «Перечисления упорядоченных деревьев», Дискретная математика , 31 : 9–28, doi : 10.1016/0012-365x(80)90168-5, hdl : 2027/uiuo.ark:/13960/t3kw6z60d
10. Дворецкий, Арье; Моцкин, Теодор (1947), «Проблема расположения», Duke Mathematical Journal , 14 (2): 305–313, doi : 10.1215/s0012-7094-47-01423-3
11. Дершовиц, Нахум; Закс, Шмуэль (январь 1990 г.). «Лемма о цикле и некоторые приложения» (PDF) . Европейский журнал комбинаторики . 11 (1): 35–40. дои : 10.1016/S0195-6698(13)80053-4.
12. Стэнли, Ричард П. (2021). «Исчислительная и алгебраическая комбинаторика в 1960-х и 1970-х годах». arXiv : 2105.07884 [math.HO].
13. Ларкомб, Питер Дж. «Китайское открытие каталонских чисел в XVIII веке» (PDF) .
14. «Минг Анту, первый изобретатель каталонских чисел в мире» . Архивировано из оригинала 31 января 2020 г. Проверено 24 июня 2014 г.
15. Чен, Синь; Ван, Джейн (2012). «Суперкаталонские числа S(m, m + s) для s ≤ 4». arXiv : 1208.4196 [math.CO].
16. Георгичук, Ирина; Ореловиц, Гидон (2020). «Суперкаталанские числа третьего и четвертого рода». arXiv : 2008.00133 [math.CO].
17. Сергей Фомин и Натан Ридинг, «Корневые системы и обобщенные ассоциэдры», Геометрическая комбинаторика, IAS/Park City Math. Сер. 13 , Американское математическое общество , Провиденс, Род-Айленд, 2007, стр. 63–131. arXiv : math/0505518
18. Чой, Хаёнг; Да, Ён-Нан; Ю, Сонгук (2020), «Каталонские числовые последовательности и последовательности моментов Хаусдорфа», Discrete Mathematics , 343 (5): 111808, 11, arXiv : 1809.07523 , doi : 10.1016/j.disc.2019.111808, MR  4052255, S2CID  2 14165563
19. Боуман, Д.; Регев, Алон (2014). «Счет симметрии: классы разрезов выпуклого правильного многоугольника». Адв. Прил. Математика . 56 : 35–55. arXiv : 1209.6270 . дои : 10.1016/j.aam.2014.01.004 . S2CID  15430707.

Рекомендации

• Стэнли, Ричард П. (2015), Каталонские цифры . Издательство Кембриджского университета, ISBN 978-1-107-42774-7 . 
• Конвей и Гай (1996) Книга чисел . Нью-Йорк: Коперник, стр. 96–106.
• Гарднер, Мартин (1988), Путешествие во времени и другие математические недоумения, Нью-Йорк: WH Freeman and Company, стр. 253–266 (гл. 20), Bibcode : 1988ttom.book.....G, ISBN 0-7167-1924-Х
• Коши, Томас (2008), каталонские числа с приложениями, Oxford University Press, ISBN 978-0-19-533454-8
• Коши, Томас и Чжэньгуан Гао (2011) «Некоторые свойства делимости каталонских чисел», Mathematical Gazette 95:96–102.
• Ларкомб, П.Дж. (1999). «Китайское открытие каталонских чисел в XVIII веке» (PDF) . Математический спектр . 32 : 5–7.
• Стэнли, Ричард П. (1999), Перечислительная комбинаторика. Том. 2, Кембриджские исследования по высшей математике, том. 62, Издательство Кембриджского университета , ISBN 978-0-521-56069-6, МР  1676282
• Эгечиоглу, Омер (2009), Оценка детерминанта Каталонии – Ханкеля (PDF)
• Георгичук, Ирина; Ореловиц, Гидон (2020), Суперкаталонские числа третьего и четвертого рода , arXiv : 2008.00133

Внешние ссылки

• Стэнли, Ричард П. (1998), каталонское приложение к перечислительной комбинаторике, том 2 (PDF)
• Вайсштейн, Эрик В. «Каталонский номер». Математический мир .
• Дэвис, Том: Каталонские числа. Еще примеры.
• «Эквивалентность трех интерпретаций каталонских чисел» из демонстрационного проекта Wolfram [1]
• Учебные материалы, связанные с числовыми треугольниками, связанными с разделами, в Викиверситете