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

 В комбинаторике, Числа Нараяны 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, что равно числу Каталана C4.

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


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


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