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

Число Нараяны
Назван в честь	Тадепалли Венката Нараяна
Количество известных терминов	бесконечность
Формула
ОЭИС Индекс	А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$ сетка, не выходящая за пределы диагонали.

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

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

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

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

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

Перегородки

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

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

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

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

\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}}\;.

См. также

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

Цитаты

^ Петерсен 2015 , стр. 25.

Ссылки

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

[FOOTNOTEPetersen201525-1] Петерсен 2015 , стр. 25.

[1]