Треугольник Каталана

В комбинаторной математике треугольник Каталана — это числовой треугольник , элементы которого дают число строк, состоящих из n X и k Y, таких, что ни один начальный сегмент строки не имеет больше Y, чем X. Это обобщение чисел Каталана , и названо в честь Эжена Шарля Каталана . Бейли ^[1] показывает, что удовлетворяют следующим свойствам: ${\displaystyle C(n,k)}$ ${\displaystyle C(n,k)}$

1. ${\displaystyle C(n,0)=1{\text{ for }}n\geq 0}$.
2. ${\displaystyle C(n,1)=n{\text{ for }}n\geq 1}$.
3. ${\displaystyle C(n+1,k)=C(n+1,k-1)+C(n,k){\text{ for }}1<k<n+1}$
4. ${\displaystyle C(n+1,n+1)=C(n+1,n){\text{ for }}n\geq 1}$.

Формула 3 показывает, что запись в треугольнике получается рекурсивно путем добавления чисел слева и сверху в треугольнике. Самое раннее появление каталонского треугольника вместе с рекурсивной формулой находится на странице 214 трактата по исчислению, опубликованного в 1800 году ^[2] Луи Франсуа Антуаном Арбогастом .

Шапиро ^[3] вводит еще один треугольник, который он называет каталонским треугольником, и который отличается от обсуждаемого здесь треугольника.

Общая формула

Общая формула для имеет вид ^{[1] [4]} ${\displaystyle C(n,k)}$

${\displaystyle C(n,k)={\binom {n+k}{k}}-{\binom {n+k}{k-1}}}$

Так

${\displaystyle C(n,k)={\frac {n-k+1}{n+1}}{\binom {n+k}{k}}}$

Когда , диагональ C ( n , n ) является n -ым каталонским числом . ${\displaystyle k=n}$

Сумма строк n -й строки является ( n + 1) -м каталонским числом , используя тождество хоккейной клюшки и альтернативное выражение для каталонских чисел.

Таблица значений

Некоторые значения приведены в ^[5]

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

• Формулу 3 из первого раздела можно использовать для доказательства обоих

${\displaystyle C(n,k)=\sum _{i=0}^{k}C(n-1,i)=\sum _{i=k}^{n}C(i,k-1)}$

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

• Если , то на каком-то этапе Y должно быть больше, чем X , поэтому . ${\displaystyle k>n}$ ${\displaystyle C(n,k)=0}$

• Комбинаторная интерпретация -го значения - это число неубывающих разбиений с ровно n частями с максимальной частью k, такой, что каждая часть меньше или равна своему индексу. Так, например, подсчитывается ${\displaystyle (n,k-1)}$ ${\displaystyle (4,2)=9}$

${\displaystyle 1111,1112,1113,1122,1123,1133,1222,1223,1233}$

Обобщение

Трапеции Каталана — это счетное множество числовых трапеций, которые обобщают треугольник Каталана. Трапеция Каталана порядка m = 1, 2, 3, ... — это числовая трапеция, элементы которой дают число строк, состоящих из n X и k Y, таких, что в каждом начальном сегменте строки число Y не превышает числа X на m или более. ^[6] По определению трапеция Каталана порядка m = 1 является треугольником Каталана, т. е . . ${\displaystyle C_{m}(n,k)}$ ${\displaystyle C_{1}(n,k)=C(n,k)}$

Некоторые значения трапеции Каталана порядка m = 2 задаются формулой

Некоторые значения трапеции Каталана порядка m = 3 задаются формулой

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

Общая формула для имеет вид ${\displaystyle C_{m}(n,k)}$

${\displaystyle C_{m}(n,k)={\begin{cases}\left({\begin{array}{c}n+k\\k\end{array}}\right)&\,\,\,0\leq k<m\\\\\left({\begin{array}{c}n+k\\k\end{array}}\right)-\left({\begin{array}{c}n+k\\k-m\end{array}}\right)&\,\,\,m\leq k\leq n+m-1\\\\0&\,\,\,k>n+m-1\end{cases}}}$

( n = 0, 1, 2, ... , k = 0, 1, 2, ... , m = 1, 2, 3, ... ).

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

Доказательство 1

Это доказательство включает расширение метода отражения Андре , который использовался во втором доказательстве для числа Каталана, для различных диагоналей. Ниже показано, как каждый путь из нижнего левого угла в верхний правый угол диаграммы, который пересекает ограничение, может также быть отражен в конечную точку . ${\displaystyle (0,0)}$ ${\displaystyle (k,n)}$ ${\displaystyle n-k+m-1=0}$ ${\displaystyle (n+m,k-m)}$

Мы рассмотрим три случая, чтобы определить количество путей из в , которые не пересекают ограничение: ${\displaystyle (0,0)}$ ${\displaystyle (k,n)}$

(1) когда ограничение невозможно пересечь, поэтому все пути от до допустимы, т.е. . ${\displaystyle m>k}$ ${\displaystyle (0,0)}$ ${\displaystyle (k,n)}$ ${\displaystyle C_{m}(n,k)=\left({\begin{array}{c}n+k\\k\end{array}}\right)}$

(2) когда невозможно сформировать путь, не пересекающий ограничение, т.е. . ${\displaystyle k-m+1>n}$ ${\displaystyle C_{m}(n,k)=0}$

(3) когда , то — это число «красных» путей минус число «желтых» путей, пересекающих ограничение, т.е. . ${\displaystyle m\leq k\leq n+m-1}$ ${\displaystyle C_{m}(n,k)}$ ${\displaystyle \left({\begin{array}{c}n+k\\k\end{array}}\right)}$ ${\displaystyle \left({\begin{array}{c}(n+m)+(k-m)\\k-m\end{array}}\right)=\left({\begin{array}{c}n+k\\k-m\end{array}}\right)}$

Следовательно, количество путей от до , не пересекающих ограничение , равно формуле, указанной в предыдущем разделе « Обобщение ». ${\displaystyle (0,0)}$ ${\displaystyle (k,n)}$ ${\displaystyle n-k+m-1=0}$

Доказательство 2

Во-первых, мы подтверждаем справедливость рекуррентного соотношения , разбив его на две части: первую для комбинаций XY, заканчивающихся на X, и вторую для тех, которые заканчиваются на Y. Таким образом, первая группа имеет действительные комбинации, а вторая имеет . Доказательство 2 завершается проверкой того, что решение удовлетворяет рекуррентному соотношению и подчиняется начальным условиям для и . ${\displaystyle C_{m}(n,k)=C_{m}(n-1,k)+C_{m}(n,k-1)}$ ${\displaystyle C_{m}(n,k)}$ ${\displaystyle C_{m}(n-1,k)}$ ${\displaystyle C_{m}(n,k-1)}$ ${\displaystyle C_{m}(n,0)}$ ${\displaystyle C_{m}(0,k)}$

Ссылки

1. Bailey, DF (1996). «Подсчет расположений единиц и -1». Mathematics Magazine . 69 (2): 128–131. doi :10.1080/0025570X.1996.11996408.
2. Арбогаст, LFA (1800). Вычисление дериваций. Левро. п. 214.
3. Шапиро, Л. В. (1976). «Каталонский треугольник». Дискретная математика . 14 (1): 83–90. doi : 10.1016/0012-365x(76)90009-1 .
4. Эрик В. Вайсштейн. «Треугольник Каталана». MathWorld − Веб-ресурс Wolfram . Получено 28 марта 2012 г.
5. Sloane, N. J. A. (ред.). "Последовательность A009766 (треугольник Каталана)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS . Получено 28 марта 2012 г.
6. Реувени, Шломи (2014). «Трапеции Каталана». Вероятность в инженерных и информационных науках . 28 (3): 4391–4396. doi :10.1017/S0269964814000047. S2CID  122765015.