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

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

Назван в честь	Тадепалли Венката Нараяна
Количество известных терминов	бесконечность
Формула	$\operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}$
ОЭИС Индекс	А001263 Треугольник Нараяны

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

Формула

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

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

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

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

н	к
	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 )

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

Слова Дайка

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

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

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

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

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

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

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

Монотонные решетчатые пути

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

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

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

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

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

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

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

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

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

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

Разделы

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

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

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

Генерирующая функция

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

$\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 Basel. Базель: Биркхойзер. дои : 10.1007/978-1-4939-3091-3 . ISBN  978-1-4939-3090-6 .