Polynôme de Narayana

Les polynômes de Narayana sont une suite de polynômes dont les coefficients sont les nombres de Narayana. Les nombres de Narayana et les polynômes de Narayana portent le nom du mathématicien canadien T. V. Narayana (1930-1987). Essentiellement liés aux nombres de Catalan, dont ils sont un raffinement, ils apparaissent dans plusieurs problèmes combinatoires^[1],[2],[3].

Étant donné un entier naturel non nul ${\displaystyle n}$ et un entier naturel ${\displaystyle k}$, le nombre de Narayana ${\displaystyle N(n,k)}$ est défini par

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

Par convention, le nombre ${\displaystyle N(0,k)}$ est défini comme valant ${\displaystyle 1}$ si ${\displaystyle k=0}$ et ${\displaystyle 0}$ si ${\displaystyle k>0}$.

Pour un entier naturel ${\displaystyle n}$, le ${\displaystyle n}$-ième polynôme de Narayana ${\displaystyle N_{n}(z)}$ est défini par

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

Le ${\displaystyle n}$-ième polynôme de Narayana associé ${\displaystyle {\mathcal {N}}_{n}(z)}$ est défini comme le polynôme réciproque de ${\displaystyle N_{n}(z)}$ :

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

Les premiers polynômes de Narayana sont :

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

Quelques-unes des propriétés des polynômes de Narayana et des polynômes de Narayana associés sont rassemblées ci-dessous. On trouve de plus amples informations sur les propriétés de ces polynômes dans les références citées.

Les polynômes de Narayana peuvent être exprimés de la façon suivante^[4] :

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

• ${\displaystyle N_{n}(1)}$ est le ${\displaystyle n}$-ième nombre de catalan ${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}}$. Les premiers nombres de Catalan sont ${\displaystyle 1,1,2,5,14,42,132,429,\ldots }$ – ils forme la suite A000108 de l'OEIS^[5] ;
• ${\displaystyle N_{n}(2)}$ est le ${\displaystyle n}$-ième grand nombre de Schröder. C'est le nombre d'arbres planaires ayant ${\displaystyle n}$ arêtes et dont les feuilles sont colorées par une ou deux couleurs. Les premiers nombres de Schröder sont ${\displaystyle 1,2,6,22,90,394,1806,8558,\ldots }$ – suite A006318 de l'OEIS^[5] ;
• pour les entiers ${\displaystyle n\geq 0}$, soit ${\displaystyle d_{n}}$ le nombre de chemins sous-diagonaux de ${\displaystyle (0,0)}$ à ${\displaystyle (n,n)}$ dans une grille ${\displaystyle n\times n}$ et formés de pas appartenant à ${\displaystyle S=\{(k,0):k\in \mathbb {N} ^{+}\}\cup \{(0,k):k\in \mathbb {N} ^{+}\}}$. Alors ${\displaystyle d_{n}={\mathcal {N}}(4)}$^[6].

• Pour ${\displaystyle n\geq 3}$, ${\displaystyle {\mathcal {N}}_{n}(z)}$ satisfait à la relation de récurrence non linéaire suivante^[1] :

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

• Pour ${\displaystyle n\geq 3}$, ${\displaystyle {\mathcal {N}}_{n}(z)}$ satisfait à la relation de récurrence linéaire du second ordre suivante^[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)}$ avec ${\displaystyle {\mathcal {N}}_{1}(z)=1}$ et ${\displaystyle {\mathcal {N}}_{2}(z)=1+z}$.

La série génératrice ordinaire des polynômes Narayana est donnée par

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

Le ${\displaystyle n}$-ième polynôme de Legendre ${\displaystyle P_{n}(x)}$ est donné par

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

Alors, pour n > 0, le polynôme de Narayana ${\displaystyle N_{n}(z)}$ peut être exprimé sous la forme suivante :

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

• Nombre de Catalan
• Nombre de Schröder

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Narayana polynomials » (voir la liste des auteurs).

• Portail des mathématiques