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

В С ₅ = 42 непересекающейся перегородкой из набора 5-элемента (ниже, остальные 10 из 52 разделов )

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

П - го числа каталонского дается непосредственно в терминах биномиальных коэффициентов по

${\ 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, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 9148256133640, 34305 4861946401452, ... (последовательность A000108 в OEIS ).

Свойства [ править ]

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

${\ displaystyle C_ {n} = {2n \ choose n} - {2n \ choose n + 1} = {1 \ over n + 1} {2n \ choose n} \ quad {\ text {for}} n \ geq 0,}$

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

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

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

${\displaystyle \sum _{i_{1}+\cdots +i_{m}=n,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}}}$

и

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

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

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

в том смысле, что частное n- го каталонского числа и выражения справа стремится к 1, когда n приближается к бесконечности. Это можно доказать, используя приближение Стирлинга для  n ! или через производящие функции .

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

Каталонские числа имеют интегральное представление

${\displaystyle C_{n}=\int _{0}^{4}x^{n}\rho (x)\,dx,}$

где Это означает, что числа Каталонии являются решением одной из версий проблемы моментов Хаусдорфа . ^[3]${\displaystyle \rho (x)={\tfrac {1}{2\pi }}{\sqrt {\tfrac {4-x}{x}}}.}$

Приложения в комбинаторике [ править ]

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

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

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

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

• Последовательные применения бинарного оператора могут быть представлены в виде полного бинарного дерева . (Бинарное дерево с корнем является полным, если каждая вершина имеет двух дочерних элементов или их нет.) Отсюда следует, что C _n - это количество полных двоичных деревьев с n  + 1 листом:

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

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

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

• Выпуклый многоугольник с п  + 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. Соединение этих двух фактов может быть использовано в доказательстве математической индукции, что все свободные кумулянты степени больше 2 закона полукруга Вигнера равны нулю. Этот закон важен в свободной теории вероятностей и теории вероятностей.случайные матрицы .
• С _п есть число способов плитки stairstep форма высоты п с п прямоугольниками. На следующем рисунке показан случай n  = 4:

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

• C _n - количество стандартных таблиц Юнга , диаграмма которых представляет собой прямоугольник размером 2 на n . Другими словами, это количество способов, которыми числа 1, 2, ..., 2 n могут быть расположены в прямоугольнике размером 2 на n так, чтобы каждая строка и каждый столбец увеличивались. Таким образом, формула может быть получена как частный случай формулы длины крючка .
• C _n - количество способов, которыми вершины выпуклого 2 n -угольника могут быть спарены так, чтобы отрезки прямых, соединяющие парные вершины, не пересекались. Это в точности условие, которое гарантирует, что парные ребра могут быть идентифицированы (сшиты вместе), чтобы сформировать замкнутую поверхность нулевого рода (топологическую 2-сферу).
• С _п есть число semiorders по п немеченых элементов. ^[7]
• В химической инженерии C _{n -1} - это количество возможных последовательностей разделения, которые могут разделить смесь из n компонентов. ^[8]

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

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

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

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

Первое доказательство [ править ]

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

${\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};}$

другими словами, это уравнение следует из рекуррентного соотношения путем разложения обеих частей в степенные ряды. С одной стороны, рекуррентное соотношение однозначно определяет каталонские числа; с другой стороны, отношение производящей функции может быть решено алгебраически, чтобы дать

${\displaystyle c(x)={\frac {1\mp {\sqrt {1-4x}}}{2x}}={\frac {2}{1\pm {\sqrt {1-4x}}}}.}$

Если выбрать знак минус (в первом выражении), дробь будет иметь степенной ряд в 0, поэтому ее коэффициенты должны быть каталонскими числами. Это решение удовлетворяет

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

Другое решение со знаком плюс имеет полюс в 0, поэтому оно не может быть допустимым решением для c ( x ).

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

${\displaystyle {\sqrt {1+y}}=\sum _{n=0}^{\infty }{{\frac {1}{2}} \choose n}y^{n}=\sum _{n=0}^{\infty }{\frac {(-1)^{n+1}}{4^{n}(2n-1)}}{2n \choose n}y^{n}=1+{\frac {1}{2}}y-{\frac {1}{8}}y^{2}+\cdots .}$

Это частный случай обобщенной биномиальной теоремы Ньютона ; как и в случае с общей теоремой, это может быть доказано вычислением производных для получения ряда Тейлора. Устанавливая y = −4 x и подставляя этот степенной ряд в выражение для c ( x ) и сдвигая индекс суммирования n на 1, разложение упрощается до

${\displaystyle c(x)=\sum _{n=0}^{\infty }{2n \choose n}{\frac {x^{n}}{n+1}}.}$

Коэффициенты теперь являются желаемой формулой для C _n .

Другой способ получить c ( x ) - найти xc ( x ) и наблюдать, что появляется в каждом члене степенного ряда.${\displaystyle \int _{0}^{x}\!t^{n}\,dt}$

Второе доказательство [ править ]

Это доказательство зависит от уловки, известной как метод отражения Андре , который первоначально использовался в связи с теоремой Бертрана о голосовании . (Принцип отражения широко приписывается Дезире Андре , но в его методе отражения фактически не использовались; а метод отражения - разновидность Эбли и Мириманофф. ^[10] ) Мы подсчитываем пути, которые начинаются и заканчиваются на диагонали п  ×  п сетки. Все такие пути имеют n ступенек вправо и n ступенек вверх. Поскольку мы можем выбрать, какой из 2 n шагов является восходящим (или, что то же самое, правым), существуют полные монотонные пути этого типа. А${\displaystyle {\tbinom {2n}{n}}}$неверный путь пересечет основную диагональ и коснется следующей более высокой ( фатальной ) диагонали (обозначенной красным на иллюстрации). Мы переворачиваем часть пути, возникшую после этого касания, по этой фатальной диагонали, как показано на рисунке; эта геометрическая операция сводится к тому, что после этого касания меняются местами все шаги вправо и вверх. На участке пути, который не отражается, на один шаг вверх больше, чем на шаги вправо, поэтому оставшийся участок неправильного пути имеет на один шаг вправо больше, чем шаг вверх (потому что он заканчивается на главной диагонали). Когда эта часть пути отражается, она также будет иметь на один шаг вверх больше, чем шаги вправо. Поскольку осталось еще 2 n шагов, теперь должно быть 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}.}$

В терминах слов Дайка мы начинаем с (не-Дейковской) последовательности n X и n Y и меняем местами все X и Y после первого Y, которое нарушает условие Дейка. В этом первом Y есть k  + 1 Y и k X для некоторого k от 1 до n  - 1.

Третье доказательство [ править ]

Следующее биективное доказательство, хотя и более сложное, чем предыдущее, дает более естественное объяснение члену n  + 1, фигурирующему в знаменателе формулы для  C _n . Обобщенную версию этого доказательства можно найти в статье Rukavicka Josef (2011). ^[11]

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

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

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

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

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

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

Это означает, что количество путей превышения n равно количеству путей превышения n  - 1, что равно количеству путей превышения n  - 2, и так далее, вплоть до нуля. Другими словами, мы разделили набор всех монотонных путей на n  + 1 классы одинакового размера, соответствующие возможным превышениям между 0 и n . Поскольку есть

${\displaystyle {2n \choose n}}$

монотонных траекторий, получаем искомую формулу

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

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

Четвертое доказательство [ править ]

В этом доказательстве используется определение триангуляции каталонских чисел, чтобы установить связь между C _n и C _{n +1} . Дан многоугольник P с n  + 2 сторонами, сначала отметьте одну из его сторон как основание. Если затем P триангулирован, мы можем дополнительно выбрать и сориентировать одно из его 2 n  + 1 ребер. Всего таких декорированных триангуляций (4 n  + 2) C _n . Теперь данный многоугольник Q с п  + 3 сторон, снова знак одной из сторон в качестве базы. Если Q триангулирован, мы можем дополнительно отметить одну из сторон, кроме основной. Есть (n  + 2) C _{n  + 1} таких декорированных триангуляций. Тогда существует простое взаимно однозначное соответствие между этими двумя видами декорированных триангуляций: мы можем либо свернуть треугольник в Q , сторона которого отмечена, либо наоборот, развернуть ориентированное ребро в P до треугольника и отметить его новую сторону. Таким образом

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

Биномиальная формула для C _n немедленно следует из этого соотношения и начального условия  C ₁  = 1.

Пятое доказательство [ править ]

Это доказательство основано на интерпретации каталонских чисел словами Дика , поэтому C _n - это количество способов правильно сопоставить n пар скобок. Мы обозначаем (возможно, пустую) правильную строку c, а ее обратную строку (где "[" и "]" меняются местами) c ⁺ . Поскольку любой c может быть однозначно разложен на c  = [  c ₁  ] c ₂ , суммирование по возможным точкам для размещения закрывающей скобки немедленно дает рекурсивное определение

${\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 обозначает сбалансированную строку длиной 2 n, то есть содержащую равное количество «[» и «]» - и с некоторым множителем d _n  ≥ 1. Как и выше, любую сбалансированную строку можно однозначно разложить на любую [  c  ]  b или]  c ⁺  [  b , поэтому${\displaystyle \textstyle B_{n}={2n \choose n}=d_{n}C_{n}}$

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

Кроме того, любая неверно сбалансированная строка начинается с c  ], поэтому

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

Вычитая приведенные выше уравнения и используя B _i = d _i C _i, получаем

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

Сравнение коэффициентов с исходной формулой рекурсии для C _n дает d _i = i + 1, поэтому

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

Шестое доказательство [ править ]

Это простое доказательство ^[12] также основано на интерпретации каталонских чисел словами Дика, но использует красивую лемму Дворецкого и Моцкина о циклах. ^[13] Назовите последовательность X и Y доминирующими, если при чтении слева направо дисбаланс всегда положительный, то есть количество X всегда строго больше, чем количество Y. Лемма о цикле утверждает, что любая последовательность X и Y, где , имеет в точности доминирующие циклические перестановки. Чтобы увидеть это, просто расположите заданную последовательность X и Y по кругу и несколько раз удалите соседние пары XY, пока не будет только${\displaystyle m}$${\displaystyle n}$${\displaystyle m>n}$${\displaystyle m-n}$${\displaystyle m+n}$${\displaystyle m-n}$Х остаются. Каждый из этих X был началом доминирующей циклической перестановки до того, как что-либо было удалено. В частности, когда существует ровно одна доминирующая циклическая перестановка. Удаление ведущего X из него (доминирующая последовательность должна начинаться с X) оставляет последовательность Дика. Поскольку существуют различные циклы X и Y, каждый из которых соответствует ровно одной последовательности Дейка, считается, что последовательности Дика.${\displaystyle m=n+1}$${\displaystyle C_{n}={\frac {1}{2n+1}}{2n+1 \choose n}={\frac {1}{n+1}}{2n \choose n}}$${\displaystyle n+1}$${\displaystyle n}$${\displaystyle C_{n}}$

Матрица Ганкеля [ править ]

П × п Ганкель матрица которого ( я ,  J ) запись является число Каталонский С _{я + J -2} имеет определитель 1, независимо от значения п . Например, для 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.}$

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

История [ править ]

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

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

Например, Мин использовал каталонскую последовательность, чтобы выразить разложение последовательностей sin (2α) и sin (4α) через sin (α).

Обобщения [ править ]

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

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

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

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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