Число Нараяны — число, выражаемое через биномиальные коэффициенты (): ; такие числа формируют треугольник Нараяны — нижнюю треугольную матрицу натуральных чисел, возникающую в ряде задач перечислительной комбинаторики.
Открыты канадским математиком индийского происхождения Тадепалли Нараяной (1930—1987) при решении следующей задачи: найти число коров и тёлок, появившихся от одной коровы за 20 лет, при условии, что корова в начале каждого года приносит тёлку, а тёлка дает такое же потомство в начале года, достигнув возраста трёх лет.
Первые восемь рядов чисел Нараяны: = 1 2 3 4 5 6 7 8 = 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, что равно числу Каталана .
Производящая функция чисел Нараяны: .
Примечания
Литература
Категория:Целочисленные последовательности