Narayana polynomials

Narayana polynomials are a class of polynomials whose coefficients are the Narayana numbers. The Narayana numbers and Narayana polynomials are named after the Canadian mathematician T. V. Narayana (1930–1987). They appear in several combinatorial problems.^[1][2][3]

Definitions

For a positive integer ${\displaystyle n}$ and for an integer ${\displaystyle k\geq 0}$, the Narayana number ${\displaystyle N(n,k)}$ is defined by

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

The number ${\displaystyle N(0,k)}$ is defined as ${\displaystyle 1}$ for ${\displaystyle k=0}$ and as ${\displaystyle 0}$ for ${\displaystyle k\neq 0}$.

For a nonnegative integer ${\displaystyle n}$, the ${\displaystyle n}$-th Narayana polynomial ${\displaystyle N_{n}(z)}$ is defined by

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

The associated Narayana polynomial ${\displaystyle {\mathcal {N}}_{n}(z)}$ is defined as the reciprocal polynomial of ${\displaystyle N_{n}(z)}$:

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

Examples

The first few Narayana polynomials are

${\displaystyle N_{0}(z)=1}$

${\displaystyle N_{1}(z)=z}$

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

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

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

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

Properties

A few of the properties of the Narayana polynomials and the associated Narayana polynomials are collected below. Further information on the properties of these polynomials are available in the references cited.

Alternative form of the Narayana polynomials

The Narayana polynomials can be expressed in the following alternative form:^[4]

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

Special values

• ${\displaystyle N_{n}(1)}$ is the ${\displaystyle n}$-th Catalan number ${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}}$. The first few Catalan numbers are ${\displaystyle 1,1,2,5,14,42,132,429,\ldots }$. (sequence A000108 in the OEIS).^[5]
• ${\displaystyle N_{n}(2)}$ is the ${\displaystyle n}$-th large Schröder number. This is the number of plane trees having ${\displaystyle n}$ edges with leaves colored by one of two colors. The first few Schröder numbers are ${\displaystyle 1,2,6,22,90,394,1806,8558,\ldots }$. (sequence A006318 in the OEIS).^[5]
• For integers ${\displaystyle n\geq 0}$, let ${\displaystyle d_{n}}$ denote the number of underdiagonal paths from ${\displaystyle (0,0)}$ to ${\displaystyle (n,n)}$ in a ${\displaystyle n\times n}$ grid having step set ${\displaystyle S=\{(k,0):k\in \mathbb {N} ^{+}\}\cup \{(0,k):k\in \mathbb {N} ^{+}\}}$. Then ${\displaystyle d_{n}={\mathcal {N}}(4)}$.^[6]

Recurrence relations

• For ${\displaystyle n\geq 3}$, ${\displaystyle {\mathcal {N}}_{n}(z)}$ satisfies the following nonlinear recurrence relation:^[6]

${\displaystyle {\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)}$.

• For ${\displaystyle n\geq 3}$, ${\displaystyle {\mathcal {N}}_{n}(z)}$ satisfies the following second order linear recurrence relation:^[6]

${\displaystyle (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)}$ with ${\displaystyle {\mathcal {N}}_{1}(z)=1}$ and ${\displaystyle {\mathcal {N}}_{2}(z)=1+z}$.

Generating function

The ordinary generating function the Narayana polynomials is given by

${\displaystyle \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}}.}$

Integral representation

The ${\displaystyle n}$-th degree Legendre polynomial ${\displaystyle P_{n}(x)}$ is given by

${\displaystyle 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}}$

Then, for n > 0, the Narayana polynomial ${\displaystyle N_{n}(z)}$ can be expressed in the following form:

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

See also

• Catalan number
• Schröder number

References