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

Число Нараяни — число, яке виражається через біноміальні коефіцієнти ( $k ⩽ n$ ):

N (n, k) = \frac{1}{n} (\binom{n}{k}) (\binom{n}{k - 1})

;

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

Відкриті канадським математиком індійського походження Тадепаллі Нараяною (1930—1987) під час розв'язування такої задачі: знайти число корів і телиць, що з'явилися від однієї корови за 20 років, за умови, що корова на початку кожного року приносить телицю, а телиця починає давати таке саме потомство на початку року при досягненні віку трьох років.

Перші вісім рядів чисел Нараяни:

Шаблон:Math =     1 2 3 4 5 6 7 8
Шаблон:Math = 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$ пар круглих дужок, які правильно зіставлені і які містять $k$ різних вкладень. Наприклад, $N (4, 2) = 6$ , оскільки чотири пари дужок утворюють шість різних послідовностей, які містять два вкладення (під вкладеннями мається на увазі шаблон ()):

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

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

N (n, k) = N (n, n - k + 1)

.

Сума рядків трикутника Нараяни дорівнює відповідним числам Каталана:

N (n, 1) + N (n, 2) + N (n, 3) + \dots + N (n, n) = C_{n}

,

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

$N (4, k)$	Шляху
$N (4, 1) = 1$ шлях з одним максимумом
$N (4, 2) = 6$ шляхів з двома максимумами
$N (4, 3) = 6$ шляхів з трьома максимумами
$N (4, 4) = 1$ шлях з чотирма максимумами