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

;

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

Відкриті канадським математиком індійського походження Тадепаллі Нараяною (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

Застосування і властивості

ред.

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

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

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

 .

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

 ,

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

  Шляху
  шлях з одним максимумом  
  шляхів з двома максимумами  
  шляхів з трьома максимумами  
  шлях з чотирма максимумами  

Сума   дорівнює 1 + 6 + 6 + 1 = 14, що дорівнює числу Каталана  .

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

ред.

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

 .

Примітки

ред.
  1. Petersen, 2015, с. 25.

Див. також

ред.

Література

ред.