WikiSort.ru - Не сортированное

В комбинаторике, Числа Нараяны N(n, k), n = 1, 2, 3 ..., 1 ≤ k ≤ n, формируют треугольную матрицу натуральных чисел, называемую Треугольником Нараяны, который всплывает во многих задачах перечислительной комбинаторики. Названы в честь индийского математика Т. В. Нараяны (1930–1987).

Историческое возникновение

В XIV веке индийский математик Нараяна решил такую задачу: найти число коров и телок, появившихся от одной коровы за 20 лет, при условии, что корова в начале каждого года приносит телку, а телка дает такое же потомство в начале года, достигнув трех лет.

Формула

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

${\displaystyle 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

Интерпретации в комбинаторике

Пример задачи подсчета, решение которой может быть задано в терминах чисел Нараяны N (n, k), - это число выражений, содержащих n пар круглых скобок, которые правильно сопоставлены и которые содержат k различных вложений. Например, N(4, 2) = 6 как четыре пары скобок образуют шесть различных последовательностей, которые содержат два вложения(под вложениями подразумевается паттерн '()'):

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

Из этого примера становится ясно, что N(n, 1) = 1, т.к. единственный способ получить только один паттерн '()' - n открывающих скобок, а затем n закрывающих. Также N(n, n) = 1, ведь единственным вариантом является последовательность ()()() ... (). В более общем случае можно показать, что треугольник Нараяны симметричен: N (n, k) = N (n, n - k + 1).

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

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

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

Фигуры получающиеся при N(4, k):

N(4, k)	Пути
N(4, 1) = 1 путь с 1 пиком:
N(4, 2) = 6 путей с 2 пиками:
N(4, 3) = 6 путей с 3 пиками:
N(4, 4) = 1 путь с 4 пиками:

Сумма N(4, k) равна 1 + 6 + 6 + 1, или 14, что равно числу Каталана C₄.

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

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

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

См. также

• Числа Каталана
• Числа Деланноя
• Числа Моцкина
• Числа Шрёдера
• Треугольник Паскаля
• Partition related number triangles

Источники

Литература

• P. A. MacMahon. Combinatorial Analysis. — Cambridge University Press, 1915–1916.
• Petersen, T. Kyle. Narayana numbers // Eulerian Numbers. — Birkhäuser, 2015. — DOI:10.1007/978-1-4939-3091-3.

Ссылки

Проект:Числа
	В Википедии есть портал «Математика» Эта статья тематически связана с Проектом:Числа, целью которого является создание качественных и информативных статей на темы, связанные с числами. Если вы хотите помочь проекту, то можете отредактировать статью, к которой относится это обсуждение, или посетить страницу проекта, где сможете, помимо прочего, присоединиться к проекту и принять участие в его обсуждении.
???	Эту статью ещё никто не оценил по шкале оценок статей Проекта:Числа.
Чем помочь: Статьи к созданию и доработке