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

Число Нараяны — число, выражаемое через биномиальные коэффициенты ($k⩽<!--\; ⩽\; -->n$$k\leqslant n$):

$N(n,k)=\frac{1}{n}(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n}{k-<!--\; -\; -->1})$$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

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

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

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

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

$N(n,k)=N(n,n-<!--\; -\; -->k+1)$$N(n,k)=N(n,n-k+1)$ .

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

$N(n,1)+N(n,2)+N(n,3)+\cdots <!--\; \cdots \; -->+N(n,n)=C_n$$N(n,1)+N(n,2)+N(n,3)+\cdots +N(n,n)=C_{n}$ ,

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

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

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

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

$\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}N(n,k)z^n{t}^k=\frac{1+z(t-<!--\; -\; -->1)-<!--\; -\; -->\sqrt{1-<!--\; -\; -->2z(t+1)+z^2(t-<!--\; -\; -->1{)}^2}}{2z}$$\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. Narayana numbers // Eulerian Numbers (неопр.). — Basel: Birkhäuser  (англ.) (рус., 2015. — doi:10.1007/978-1-4939-3091-3.