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

Число Нараяни — число, яке виражається через біноміальні коефіцієнти (${\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}}$.

Твірна функція чисел Нараяни^[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}}}$.

• Числа Деланоя

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