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

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

Формула


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

N(n,k)=1n(nk)(nk1).

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


 Первые восемь рядов чисел Нараяны:
\textttk\texttt =      1   2   3   4   5   6   7   8\\\textttn\texttt = 1    1\\\texttt    2    1   1\\\texttt    3    1   3   1\\\texttt    4    1   6   6   1\\\texttt    5    1  10  20  10   1\\\texttt    6    1  15  50  50  15   1\\\texttt    7    1  21 105 175 105  21   1\\\texttt    8    1  28 196 490 490 196  28   1

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


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

N(n,1)+N(n,2)+N(n,3)++N(n,n)=Cn.
 Иллюстрируя это соотношение, числа Нараяны также подсчитывают количествопутей от (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\textsubscript4.

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


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


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