Число Нараяны

В комбинаторике , то число нарайано образует треугольную матрицу из натуральных чисел , называется Нараян треугольником, которые возникают в различных задачах подсчета . Они названы в честь канадского математика Т. В. Нараяна (1930–1987).${\ displaystyle \ operatorname {N} (n, k), n \ in \ mathbb {N} ^ {+}, 1 \ leq k \ leq n}$

Формула [ править ]

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

${\displaystyle \operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}}$

Числовые значения [ править ]

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

k = 1 2 3 4 5 6 7 8 n = 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 )

Комбинаторные интерпретации [ править ]

Слова Дайка [ править ]

Примером задачи подсчета, решение которой может быть дано в терминах чисел Нараяны , является количество слов, содержащих пары скобок, которые правильно сопоставлены (известные как слова Дайка ) и которые содержат различные вложения. Например, поскольку с четырьмя парами круглых скобок можно создать шесть последовательностей, каждая из которых содержит два вхождения подшаблона :${\displaystyle \operatorname {N} (n,k)}$${\displaystyle n}$${\displaystyle k}$${\displaystyle \operatorname {N} (4,2)=6}$()

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

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

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

${\displaystyle \operatorname {N} (n,k)=\operatorname {N} (n,n-k+1)}$

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

${\displaystyle \operatorname {N} (n,1)+\operatorname {N} (n,2)+\operatorname {N} (n,3)+\cdots +\operatorname {N} (n,n)=C_{n}}$

Монотонные решетчатые траектории [ править ]

Числа Нараяны также подсчитывают количество путей решетки от до , со ступенями только на северо-восток и юго-восток, не отклоняясь ниже оси x , с пиками.${\displaystyle (0,0)}$${\displaystyle (2n,0)}$${\displaystyle k}$

На следующих рисунках представлены числа Нараяны , иллюстрирующие вышеупомянутые симметрии.${\displaystyle \operatorname {N} (4,k)}$

${\displaystyle \operatorname {N} (4,k)}$	Пути
N (4, 1) = 1 путь с 1 вершиной
N (4, 2) = 6 путей с 2 ​​вершинами:
N (4, 3) = 6 путей с 3 вершинами:
N (4, 4) = 1 путь с 4 вершинами:

Сумма 1 + 6 + 6 + 1 = 14, что является четвертым каталонским числом . Эта сумма совпадает с интерпретацией каталонских чисел как количества монотонных путей по краям сетки, которые не проходят выше диагонали.${\displaystyle \operatorname {N} (4,k)}$${\displaystyle C_{4}}$${\displaystyle n\times n}$

Деревья с корнями [ править ]

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

Количество немаркированных упорядоченных корневых деревьев с ребрами и листьями равно .${\displaystyle n}$${\displaystyle k}$${\displaystyle \operatorname {N} (n,k)}$

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

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

• На приведенных выше рисунках путей решетки каждое восходящее ребро от горизонтальной линии на высоте до соответствует ребру между узлом и его дочерним элементом. У узла столько потомков, сколько восходящих ребер отходят от горизонтальной линии на высоте . Например, в первом пути для узлов 0 и 1 будет по два дочерних элемента; в последнем (шестом) пути узел 0 будет иметь трех дочерних элементов, а узел 1 будет иметь одного ребенка. Чтобы построить корневое дерево из пути решетки и наоборот, мы можем использовать алгоритм, аналогичный тому, который упоминался в предыдущем абзаце. Как и в случае со словами Дика, существует изоморфизм между путями в решетке и корневыми деревьями.${\displaystyle y}$${\displaystyle y}$${\displaystyle +1}$${\displaystyle y}$${\displaystyle y}$${\displaystyle y}$${\displaystyle \operatorname {N} (4,3)}$

Разделы [ править ]

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

Изучая разбиения, мы видим, что в наборе, содержащем элементы, мы можем разбить этот набор по- разному, где - ^th число Белла . Кроме того, для определения количества способов разбить набор на ровные блоки мы используем числа Стирлинга . Обе эти концепции немного не по теме, но являются необходимой основой для понимания использования чисел Нараяны. В обоих вышеупомянутых двух понятиях учитываются пересечения перегородок.${\displaystyle n}$${\displaystyle B_{n}}$${\displaystyle B_{n}}$${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle S(n,k)}$

Отвергнуть разделы пересечения и рассчитывать только непересекающиеся разделы , мы можем использовать номера каталонских сосчитать непересекающиеся разделы всех элементов множества, . Для подсчета непересекающихся разбиений, в которых набор разбивается ровно на блоки, мы используем число Нараяны .${\displaystyle n}$${\displaystyle C_{n}}$${\displaystyle k}$${\displaystyle \operatorname {N} (n,k)}$

Функция генерации [ править ]

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

${\displaystyle \sum _{n=1}^{\infty }\sum _{k=1}^{n}\operatorname {N} (n,k)z^{n}t^{k-1}={\frac {1-z(t+1)-{\sqrt {1-2z(t+1)+z^{2}(t-1)^{2}}}}{2tz}}\;.}$

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

• Каталонский номер
• Число Деланного
• Число Моцкина
• Число Шредера
• Треугольник Паскаля
• Учебные материалы по числовым треугольникам, связанным с разделами, в Викиверситете

Цитаты [ править ]

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

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