Narayana polynomials

For a positive integer $n$ and for an integer $k\backslash geq0$, the Narayana number $N(n,k)$ is defined by

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

The number $N(0,k)$ is defined as $1$ for $k=0$ and as $0$ for $k\backslash ne0$.

For a nonnegative integer $n$, the $n$-th Narayana polynomial $N\_n(z)$ is defined by

:$N\_n(z)\; =\; \backslash sum\_\{k=0\}^n\; N(n,k)z^k.$

The associated Narayana polynomial $\backslash mathcal\; N\_n(z)$ is defined as the reciprocal polynomial of $N\_n(z)$:

:$\backslash mathcal\; N\_n(z)=z^nN\_n\backslash left(\backslash tfrac\{1\}\{z\}\backslash right)$.

The first few Narayana polynomials are

:$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$

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.

The Narayana polynomials can be expressed in the following alternative form:{{cite arXiv |last1=Ricky X. F. Chen and Christian M. Reidys |title=Narayana polynomials and some generalizations |date=2014 |class=math.CO |eprint=1411.2530 }}

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

• $N\_n(1)$ is the $n$-th Catalan number $C\_n=\backslash frac\{1\}\{n+1\}\{2n\; \backslash choose\; n\}$. The first few Catalan numbers are $1,\; 1,\; 2,\; 5,\; 14,\; 42,\; 132,\; 429,\; \backslash ldots$. {{OEIS|id=A000108}}.{{cite arXiv |last1=Toufik Mansour, Yidong Sun |title=Identities involving Narayana polynomials and Catalan numbers |date=2008 |class=math.CO |eprint=0805.1274 }}
• $N\_n(2)$ is the $n$-th large Schröder number. This is the number of plane trees having $n$ edges with leaves colored by one of two colors. The first few Schröder numbers are $1,\; 2,\; 6,\; 22,\; 90,\; 394,\; 1806,\; 8558,\; \backslash ldots$. {{OEIS|id=A006318}}.
• For integers $n\backslash ge\; 0$, let $d\_n$ denote the number of underdiagonal paths from $(0,0)$ to $(n,n)$ in a $n\backslash times\; n$ grid having step set $S\; =\; \backslash \{(k,\; 0)\; :\; k\; \backslash in\; \backslash mathbb\; N^+\backslash \}\; \backslash cup\; \backslash \{(0,\; k)\; :\; k\; \backslash in\; \backslash mathbb\; N^+\backslash \}$. Then $d\_n\; =\; \backslash mathcal\; N(4)$.{{cite journal |last1=Curtis Coker |title=Enumerating a class oflattice paths |journal=Discrete Mathematics |date=2003 |volume=271 |issue=1–3 |pages=13–28 |doi=10.1016/S0012-365X(03)00037-2 |url=https://core.ac.uk/download/pdf/82292598.pdf |access-date=1 December 2023}}

• For $n\; \backslash ge\; 3$, $\backslash mathcal\; N\_n(z)$ satisfies the following nonlinear recurrence relation:

:$\backslash mathcal\; N\_n(z)\; =\; (1+z)N\_\{n-1\}(z)\; +\; z\; \backslash sum\_\{k=1\}^\{n-2\}\backslash mathcal\; N\_k(z)\backslash mathcal\; N\_\{n-k-1\}(z)$.

• For $n\backslash ge\; 3$, $\backslash mathcal\; N\_n(z)$ satisfies the following second order linear recurrence relation:

:$(n+1)\backslash mathcal\; N\_n(z)\; =\; (2n-1)(1+z)\backslash mathcal\; N\_\{n-1\}(z)\; -\; (n-2)(z-1)^2\backslash mathcal\; N\_\{n-2\}(z)$ with $\backslash mathcal\; N\_1(z)=1$ and $\backslash mathcal\; N\_2(z)=1+z$.

The ordinary generating function the Narayana polynomials is given by

: $\backslash sum\_\{n=0\}^\{\backslash infty\}\; N\_n(z)t^n\; =\; \backslash frac\{1+t-t\; z\; -\backslash sqrt\{1\; -\; 2(1+z)\; t\; +\; (1-z)^2\; t^2\; \}\}\{2\; t\}.$

The $n$-th degree Legendre polynomial $P\_n(x)$ is given by

:$P\_n(x)\; =\; 2^\{-n\}\backslash sum\_\{k=0\}^\{\backslash left\backslash lfloor\; \backslash frac\{n\}\{2\}\backslash right\backslash rfloor\; \}\; (-1)^k\; \{n-k\; \backslash choose\; k\}\{2n-2k\; \backslash choose\; n-k\}x^\{n-2k\}$

Then, for n > 0, the Narayana polynomial $N\_n(z)$ can be expressed in the following form:

• $N\_n(z)=(z-1)^\{n+1\}\backslash int\_0^\{\backslash frac\{z\}\{z-1\}\}\; P\_n(2x-1)\backslash ,dx$.

• Catalan number
• Schröder number

{{reflist|colwidth=30em}}

Category: Polynomials