Ru.Wikipedia.Org - Число Нараяны

Меню
Главная
Случайная статья
Настройки

Число Нараяны
Материал из https://ru.wikipedia.org

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

k\leqslant n

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

;

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

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

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

k =       1   2   3   4   5   6   7   8

Приложения и свойства

Пример задачи подсчёта, решение которой может быть задано в терминах чисел Нараяны

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}

.

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

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

Примечания

последовательность A001263 в OEIS
Petersen, 2015, p. 25.

Литература

P. A. MacMahon. Combinatorial Analysis (неопр.) . — Cambridge University Press, 1915–1916.