Русская Википедия:Число Нараяны

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Число Нараяны — число, выражаемое через биномиальные коэффициенты (<math>k\leqslant n</math>):

<math>N(n,k) = \frac{1}{n}{n\choose k}{n\choose k-1}</math>;

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

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

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

Шаблон:Mvar =       1   2   3   4   5   6   7   8
Шаблон:Mvar = 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

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

Пример задачи подсчёта, решение которой может быть задано в терминах чисел Нараяны <math>N (n, k)</math>, — это число выражений, содержащих <math>n</math> пар круглых скобок, которые правильно сопоставлены и которые содержат <math>k</math> различных вложений. Например, <math>N(4,2)=6</math> как четыре пары скобок образуют шесть различных последовательностей, которые содержат два вложения(под вложениями подразумевается шаблон ()):

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

Пример демонстрирует, что <math>N(n,1) = 1</math>, так как единственный способ получить только один шаблон () — <math>n</math> открывающих скобок, а затем <math>n</math> закрывающих. Также <math>N(n, n)=1</math>, поскольку единственным вариантом является последовательность ()()() … (). В более общем случае можно показать, что треугольник Нараяны обладает следующим свойством симметрии:

<math>N(n,k)=N(n,n-k+1)</math>.

Сумма строк треугольника Нараяны равняется соответствующим числам Каталана:

<math>N(n,1) + N(n,2) + N(n,3) + \cdots + N(n,n) = C_n</math>,

таким образом, числа Нараяны также подсчитывают количество путей на двумерной целочисленной решётке от <math>(0, 0)</math> до <math>(2n, 0)</math> при движении только по северо-восточной и юго-восточной диагоналям, не отклоняясь ниже оси абсцисс, с <math>k</math> локальными максимумами. Фигуры получающиеся при <math>N(4,k)</math>:

<math>N(4,k)</math>	Пути
<math>N(4,1)=1</math> путь с одним максимумом:	Файл:Narayana N(4, 1).svg
<math>N(4,2)=6</math> путей с двумя максимумами:	Файл:Narayana N(4, 2).svg
<math>N(4,3)=6</math> путей с тремя максимумами:	Файл:Narayana N(4, 3).svg
<math>N(4,4)=1</math> путь с четырьмя максимумами:	Файл:Narayana N(4, 4).svg

Сумма <math>N(4,k)</math> равна 1 + 6 + 6 + 1 = 14, что равно числу Каталана <math>C_4</math>.

Производящая функция чисел НараяныШаблон:Sfn:

<math>

\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} </math>.

Литература

• Шаблон:Книга
• Шаблон:Книга