Число Нараяны (Cnvlk Ugjgxud)

Перейти к навигации Перейти к поиску

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

;

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

Открыты канадским математиком индийского происхождения Тадепалли Нараяной (1930—1987) при решении следующей задачи: найти число коров и тёлок, появившихся от одной коровы за 20 лет, при условии, что корова в начале каждого года приносит тёлку, а тёлка дает такое же потомство в начале года, достигнув возраста трёх лет.

Первые восемь рядов чисел Нараяны[1]:

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, что равно числу Каталана .

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

.

Примечания

[править | править код]
  1. последовательность A001263 в OEIS
  2. Petersen, 2015, p. 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.