Полиномы Нараяны

Полиномы Нараяны — это класс многочленов, коэффициентами которых являются числа Нараяны . Числа Нараяны и полиномы Нараяны названы в честь канадского математика Т.В. Нараяны (1930–1987). Они появляются в ряде комбинаторных задач.

Определения

Для положительного целого числа $n$ и для целого числа $k\geq 0$, число Нараяны $N(n,k)$ определяется

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

Число $N(0,k)$ определяется как $1$ для $k=0$ и как $0$ для $k\neq 0$.

Для неотрицательного целого числа $n$, $n$-й полином Нараяны $N_{n}(z)$ определяется

$N_{n}(z)=\sum _{k=0}^{n}N(n,k)z^{k}.$

Соответствующий полином Нараяны ${\mathcal {N}}_{n}(z)$ определяется как обратный полином $N_{n}(z)$:

${\mathcal {N}}_{n}(z)=z^{n}N_{n}\left({\tfrac {1}{z}}\right)$.

Примеры

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

$N_{0}(z)=1$

$N_{1}(z)=z$

$N_{2}(z)=z^{2}+z$

$N_{3}(z)=z^{3}+3z^{2}+z$

$N_{4}(z)=z^{4}+6z^{3}+6z^{2}+z$

$N_{5}(z)=z^{5}+10z^{4}+20z^{3}+10z^{2}+z$

Характеристики

Некоторые свойства полиномов Нараяны и связанных с ними полиномов Нараяны собраны ниже. Дополнительную информацию о свойствах этих полиномов можно найти в цитируемых ссылках.

Альтернативная форма полиномов Нараяны

Полиномы Нараяны можно выразить в следующей альтернативной форме:

• $N_{n}(z)=\sum _{0}^{n}{\frac {1}{n+1}}{n+1 \choose k}{2n-k \choose n}(z-1)^{k}$

Особые значения

• $N_{n}(1)$ это $n$-й каталонский номер $C_{n}={\frac {1}{n+1}}{2n \choose n}$. Первые несколько каталонских чисел: $1,1,2,5,14,42,132,429,\ldots$. (последовательность A000108 в OEIS ).
• $N_{n}(2)$ это $n$-е большое число Шредера . Это количество платанов, имеющих $n$ края с листьями, окрашенными в один из двух цветов. Первые несколько чисел Шредера $1,2,6,22,90,394,1806,8558,\ldots$. (последовательность A006318 в OEIS ).
• Для целых чисел $n\geq 0$, позволять $d_{n}$ обозначим количество недодиагональных путей из $(0,0)$ к $(n,n)$ в $n\times n$ сетка с заданным шагом $S=\{(k,0):k\in \mathbb {N} ^{+}\}\cup \{(0,k):k\in \mathbb {N} ^{+}\}$. Затем $d_{n}={\mathcal {N}}(4)$.

Рекуррентные отношения

• Для $n\geq 3$, ${\mathcal {N}}_{n}(z)$ удовлетворяет следующему нелинейному рекуррентному соотношению:

${\mathcal {N}}_{n}(z)=(1+z)N_{n-1}(z)+z\sum _{k=1}^{n-2}{\mathcal {N}}_{k}(z){\mathcal {N}}_{n-k-1}(z)$.

• Для $n\geq 3$, ${\mathcal {N}}_{n}(z)$ удовлетворяет следующему линейному рекуррентному соотношению второго порядка:

$(n+1){\mathcal {N}}_{n}(z)=(2n-1)(1+z){\mathcal {N}}_{n-1}(z)-(n-2)(z-1)^{2}{\mathcal {N}}_{n-2}(z)$ с ${\mathcal {N}}_{1}(z)=1$ и ${\mathcal {N}}_{2}(z)=1+z$.

Генерирующая функция

Обычная производящая функция полиномов Нараяны имеет вид

$\sum _{n=0}^{\infty }N_{n}(z)t^{n}={\frac {1+t-tz-{\sqrt {1-2(1+z)t+(1-z)^{2}t^{2}}}}{2t}}.$

Интегральное представление

The $n$ -й степени Полином Лежандра $P_{n}(x)$ дается

$P_{n}(x)=2^{-n}\sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }(-1)^{k}{n-k \choose k}{2n-2k \choose n-k}x^{n-2k}$

Тогда при n > 0 полином Нараяны $N_{n}(z)$ можно выразить в следующей форме:

• $N_{n}(z)=(z-1)^{n+1}\int _{0}^{\frac {z}{z-1}}P_{n}(2x-1)\,dx$.

См. также

• Каталонский номер
• число Шредера