Число Нараяны - Narayana number - Wikipedia

В комбинаторика, то Числа Нараяны сформировать треугольная решетка из натуральные числа, называется Треугольник Нараяны, которые происходят в различных проблемы с подсчетом. Они названы в честь Канадский математик Т. В. Нараяна (1930–1987).

Формула

Числа Нараяны могут быть выражены через биномиальные коэффициенты:

Числовые значения

Первые восемь рядов треугольника Нараяны гласят:

k =       1   2   3   4   5   6   7   8п = 1  |  1    2  |  1   1    3  |  1   3   1    4  |  1   6   6   1    5  |  1  10  20  10   1    6  |  1  15  50  50  15   1    7  |  1  21 105 175 105  21   1    8  |  1  28 196 490 490 196  28   1

(последовательность A001263 в OEIS )

Комбинаторные интерпретации

Слова Дайка

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

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

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

В более общем плане можно показать, что треугольник Нараяны симметричен:

Сумма строк в этом треугольнике равна Каталонские числа:

Монотонные решетчатые траектории

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

Следующие рисунки представляют числа Нараяны. , иллюстрирующий упомянутые выше симметрии.

Пути
N(4, 1) = 1 дорожка с 1 вершинойНараяна Н (4, 1) .svg
N(4, 2) = 6 пути с 2 вершинами:Нараяна Н (4, 2) .svg
N(4, 3) = 6 пути с 3 вершинами:Нараяна Н (4, 3) .svg
N(4, 4) = 1 путь с 4 вершинами:Нараяна Н (4, 4) .svg

Сумма равно 1 + 6 + 6 + 1 = 14, что является четвертым каталонским числом, . Эта сумма совпадает с интерпретацией каталонских чисел как количества монотонных путей по краям сетка, которая не проходит выше диагонали.

Деревья с корнями

6 упорядоченных корневых деревьев с 4 ребрами и 2 листьями, соответствующими числу Нараяны N (4, 2)

Количество немаркированных упорядоченный укорененный деревья с края и листья равно .

Это аналогично приведенным выше примерам:

  • Каждое слово Дайка можно представить как корневое дерево. Начнем с единственного узла - корневого узла. Это изначально активный узел. Читая слово слева направо, когда символ является открывающей круглой скобкой, добавьте дочерний элемент к активному узлу a и установите этот дочерний элемент в качестве активного узла. Когда символ является закрывающей круглой скобкой, установите родительский элемент активного узла как активный узел. Таким образом, мы получаем дерево, в котором каждый некорневой узел соответствует соответствующей паре круглых скобок, а его дочерние элементы - это узлы, соответствующие последовательным словам Дика в этих скобках. Узлы листа соответствуют пустым скобкам: (). Аналогичным образом мы можем построить слово Дайка из корневого дерева с помощью поиска в глубину. Таким образом, между словами Дика и корневыми деревьями существует изоморфизм.
  • На приведенных выше рисунках решетчатых дорожек каждый восходящий край от горизонтальной линии на высоте к соответствует ребру между узлами и его ребенок. Узел имеет столько дочерних элементов, сколько ребер идут вверх от горизонтальной линии на высоте . Например, в первом пути для , узлы 0 и 1 будет по двое детей; в последнем (шестом) пути узел 0 будет иметь троих детей и узел 1 будет один ребенок. Чтобы построить корневое дерево из пути решетки и наоборот, мы можем использовать алгоритм, аналогичный тому, который упоминался в предыдущем абзаце. Как и в случае со словами Дейка, существует изоморфизм между путями в решетке и корневыми деревьями.

Перегородки

1,6,6,1 непересекающиеся перегородки с 1,2,3,4,5 блоками из 4-х элементного набора

Изучая разбиения, мы видим, что в наборе, содержащем элементов, мы можем разделить этот набор в разными способами, где это th Номер звонка. Кроме того, количество способов разбить набор точно на блоки мы используем Числа Стирлинга . Обе эти концепции немного не по теме, но являются необходимой основой для понимания использования чисел Нараяны. В обоих вышеупомянутых двух понятиях учитываются пересечения перегородок.

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

Производящая функция

Производящая функция для чисел Нараяны: [1]

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

Цитаты

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

  • П. А. Мак-Магон (1915–1916). Комбинаторный анализ. Издательство Кембриджского университета.
  • Петерсен, Т. Кайл (2015). «Числа Нараяны» (PDF). Числа Эйлера. Birkhäuser Advanced Texts Basler Lehrbücher. Базель: Биркхойзер. Дои:10.1007/978-1-4939-3091-3. ISBN  978-1-4939-3090-6.