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

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

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$ пар круглих дужок, які правильно зіставлені і які містять $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)+\cdots +N(n,n)=C_{n}

,

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

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

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

Твірна функція

Твірна функція чисел Нараяни[1]:

\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}}

.

Примітки

Petersen, 2015, с. 25.

Див. також

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

Література

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[FOOTNOTEPetersen201525-1] Petersen, 2015, с. 25.