Число Нараяны — число, выражаемое через биномиальные коэффициенты ( ${\displaystyle k\leqslant n}$ ):

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

такие числа формируют треугольник Нараяны — нижнюю треугольную матрицу натуральных чисел, возникающую в ряде задач перечислительной комбинаторики .

Открыты канадским математиком индийского происхождения (1930—1987) при решении следующей задачи: найти число коров и тёлок, появившихся от одной коровы за 20 лет, при условии, что корова в начале каждого года приносит тёлку, а тёлка дает такое же потомство в начале года, достигнув возраста трёх лет.

Первые восемь рядов чисел Нараяны :

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

Приложения и свойства

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

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

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

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

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

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

таким образом, числа Нараяны также подсчитывают количество путей на двумерной целочисленной решётке от ${\displaystyle (0,0)}$ до ${\displaystyle (2n,0)}$ при движении только по северо-восточной и юго-восточной диагоналям, не отклоняясь ниже оси абсцисс , с ${\displaystyle k}$ локальными максимумами. Фигуры получающиеся при ${\displaystyle N(4,k)}$ :

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

Сумма ${\displaystyle N(4,k)}$ равна 1 + 6 + 6 + 1 = 14, что равно числу Каталана ${\displaystyle C_{4}}$ .

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

${\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}}}$ .

Примечания

Литература

• P. A. MacMahon. Combinatorial Analysis (неопр.) . — Cambridge University Press , 1915–1916.
• Petersen, T. Kyle. // Eulerian Numbers (неопр.) . — Basel: (англ.) ( , 2015. — doi : .