Каталонский треугольник - Википедия - Catalans triangle

В комбинаторная математика, Каталонский треугольник это числовой треугольник чьи записи укажите количество строк, состоящих из п Х и k Y такое, что ни один начальный сегмент строки не имеет больше Y, чем X. Это обобщение Каталонские числа, и назван в честь Эжен Шарль Каталан. Бейли[1] показывает, что удовлетворяют следующим свойствам:

  1. .
  2. .
  3. .

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

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

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

Общая формула для дан кем-то[1][4]

куда п и k неотрицательные целые числа и п! обозначает факториал. Таким образом, для k>0, .

Диагональ C(п, п) это п-го Каталонский номер. Сумма строки п-я строка - это (п + 1)-го Каталонский номер.

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

 k
п 
012345678
01
111
2122
31355
41491414
51514284242
616204890132132
7172775165297429429
81835110275572100114301430

Обобщение

Каталонские трапеции представляют собой счетный набор числовых трапеций, образующих каталонский треугольник. Каталонская трапеция порядка м = 1, 2, 3, ... числовая трапеция, элементы которой укажите количество строк, состоящих из п Икс и k Y-s такие, что в каждом начальном сегменте строки количество Y-s не превышает количества X-ов на м или больше.[6] По определению, каталонская трапеция порядка м = 1 каталонский треугольник, т.е. .

Некоторые ценности каталонской трапеции порядка м = 2 даны

 k
п 
012345678
011
1122
21355
31491414
41514284242
516204890132132
6172775165297429429
71835110275572100114301430

Некоторые ценности каталонской трапеции порядка м = 3 даны

 k
п 
0123456789
0111
11233
213699
31410192828
4151534629090
5162155117207297297
617288320040770410011001
718361193197261430243134323432

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

Общая формула для дан кем-то

( п = 0, 1, 2, ..., k = 0, 1, 2, ..., м = 1, 2, 3, ...).

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

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

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

Общее каталонское число proof.png

Рассмотрим три случая, чтобы определить количество путей из к которые не выходят за рамки ограничения:

(1) когда ограничение не может быть пересечено, поэтому все пути от к действительны, т.е. .

(2) когда невозможно сформировать путь, который не пересекает ограничение, т.е. .

(3) когда , тогда количество "красных" путей минус количество "желтых" путей, которые пересекают ограничение, т.е. .


Таким образом, количество путей от к которые не выходят за рамки ограничений как указано в формуле в предыдущем разделе "Обобщение".

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

Во-первых, мы подтверждаем справедливость рекуррентного соотношения разрушая на две части, первая для комбинаций XY, оканчивающихся на X, а вторая для тех, которые заканчиваются на Y. Таким образом, первая группа имеет допустимые комбинации, а второй . Доказательство 2 завершается проверкой того, что решение удовлетворяет рекуррентному соотношению и подчиняется начальным условиям для и .

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

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

  1. ^ а б Бейли, Д. Ф. (1996). «Счетные расстановки единиц и -1». Математический журнал. 69 (2): 128–131. Дои:10.1080 / 0025570X.1996.11996408.
  2. ^ Арбогаст, Л. Ф. А. (1800). Du Calcul des Derivations. п.214.
  3. ^ Шапиро, Л. В. (1976). "Каталонский треугольник". Дискретная математика. 14 (1): 83–90. Дои:10.1016 / 0012-365x (76) 90009-1.
  4. ^ Эрик В. Вайсштейн. «Каталонский треугольник». MathWorld - веб-ресурс Wolfram. Получено 28 марта, 2012.
  5. ^ Слоан, Н. Дж. А. (ред.). «Последовательность A009766 (каталонский треугольник)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS. Получено 28 марта, 2012.
  6. ^ Реувени, Шломи (2014). «Каталонские трапеции». Вероятность в технических и информационных науках. 28 (3): 4391–4396. Дои:10.1017 / S0269964814000047.