Nombre de Narayana

Le nombre ${\displaystyle N(n,k)}$ compte le nombre de parenthésages corrects en ${\displaystyle n}$ paires de parenthèses et qui contiennent ${\displaystyle k}$ occurrences de la paire '()'. Par exemple, ${\displaystyle N(4,2)}$ compte les mots avec 4 paires de parenthèses (donc de longueur 8) et qui contiennent exactement 2 fois la paire '()'. On a ${\displaystyle N(4,2)=6}$, les six parenthésages sont :

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

On voit facilement que ${\displaystyle N(n,1)=1}$, puisque la condition implique que toutes les parenthèses ouvrantes précèdent toutes les parenthèses fermantes. De même, ${\displaystyle N(n,n)=1}$, le seul parenthésage possible est ()() ... (). Plus généralement, on peut prouver que le triangle de Narayan est symétrique, c'est-à-dire que ${\displaystyle N(n,k)=N(n,n-k+1)}$

Si l'on représente un parenthésage par un chemin de Dyck, le nombre ${\displaystyle N(n,k)}$ compte les chemins de Dyck de longueur ${\displaystyle 2n}$ qui ont exactement ${\displaystyle k}$ pics, c'est-à-dire de pas montants suivis immédiatement d'un pas descendant. Les figures suivantes représentent les chemins comptés par les nombres ${\displaystyle N(4,k)}$ :

Les 14 partitions non croisées de 4 éléments. Il y en a 1, 6, 6, 1 en respectivement 1, 2, 3, ou 4 parts.

${\displaystyle N(4,k)}$	Chemins
${\displaystyle N(4,1)=1}$ chemin avec 1 pic :
${\displaystyle N(4,2)=6}$ chemins avec 2 pics :
${\displaystyle N(4,3)=6}$ chemins avec 3 pics :
${\displaystyle N(4,4)=1}$ chemin avec 4 pics :

Dans la partie supérieure, les 42 partitions non croisées de 5 éléments ; dans la partie inférieure, les 10 autres partitions.

On considère un ensemble ${\displaystyle S}$ à ${\displaystyle n}$ éléments qui est ordonné de manière cyclique comme les sommets d'un polygone. Une partition de ${\displaystyle S}$ est non croisée (dans la terminologie de Kreweras 1972) si deux parties de la partition ne peuvent pas se croiser au sens suivant : si ${\displaystyle a}$ et ${\displaystyle b}$ appartiennent à un bloc et ${\displaystyle x}$ et ${\displaystyle y}$ à un autre bloc, ils ne sont pas rangés dans l'ordre ${\displaystyle a\ x\ b\ y}$. En d'autres termes, si l'on trace des arcs reliant ${\displaystyle a}$ et ${\displaystyle b}$ d'une part, ${\displaystyle x}$ et ${\displaystyle y}$ d'autre part, ils ne doivent pas se croiser : ils se croisent si l'ordre est ${\displaystyle a\ x\ b\ y}$, mais ne se croisent pas si l'ordre est ${\displaystyle a\ x\ y\ b}$ ou ${\displaystyle a\ b\ x\ y}$. Les partitions non croisées forment un treillis pour l'ordre usuel de raffinement.

Le nombre de partitions non croisées d'un ensemble à ${\displaystyle n}$ éléments est le nombre de Catalan ${\displaystyle C_{n}}$. Le nombre de ces partitions non croisées comportant exactement ${\displaystyle k}$ blocs est le nombre de Narayana ${\displaystyle N(n,k)}$.

Un polyomino parallélogramme de périmètre 12, à 3 colonnes. Il figure parmi les polyominos énumérés par ${\displaystyle N(5,3)}$.

Les polyominos parallélogrammes de périmètre ${\displaystyle 2n}$ sont des tableaux de cellules unités connexes, et dont le contour est fait de deux chemins composés de pas horizontaux et verticaux qui ne se touchent qu'à leurs extrémités (donc deux contours de longueur ${\displaystyle n}$ respectivement). Les polyominos parallélogrammes de périmètre ${\displaystyle 2n+2}$ sont en bijection avec les chemins de Dyck de longueur ${\displaystyle 2n}$, et les polyominos parallélogrammes de périmètre ${\displaystyle 2n+2}$ qui ont ${\displaystyle k}$ colonnes sont comptés par les nombres de Narayana ${\displaystyle N(n,k)}$[3].

La série génératrice des nombres de Narayana est[4] :

${\displaystyle {\frac {1}{2x}}{\Big (}1-x(1+y)-{\sqrt {(1-x(1+y))^{2}-4yx^{2}}}{\Big )}=\sum _{n>0,k>0}N(n,k)x^{n}y^{k}}$.

Les polynômes de Narayana sont les fonctions génératrices des lignes du triangle de Narayana, définis par la formule

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

Ces polynômes vérifient la relation de récurrence suivante[5] :

${\displaystyle (n+1)N_{n}(x)=(2n-1)(1+x)N_{n-1}(x)-(n-2)(x-1)^{2}N_{n-2}(x)}$

avec ${\displaystyle N_{1}(x)=x}$ et ${\displaystyle N_{2}(x)=x+x^{2}}$. Cette relation s'explique par le fait que les polynômes de Narayana sont liés aux polynômes de Gegenbauer, une famille de polynômes orthogonaux[6].

• Cyril Banderier et Sylviane Schwer, « Why Delannoy numbers? », Journal of Statistical Planning and Inference, vol. 135, n^o 1,‎ 2005, p. 40-54 (arXiv math/0411128).
• Sri Gopal Mohanty, « Tadepalli Venkata Narayana 1930-1987 », Journal of Statistical Planning and Inference, vol. 101, n^os 1–2,‎ février 2002, p. 5.

• Tadepalli Venkata Narayana, « Sur les treillis formés par les partitions d'un entier et leurs applications à la théorie des probabilités », Comptes Rendus de l'Académie des Sciences Paris, vol. 240,‎ 1955, p. 1188-1189.
• Tadepalli Venkata Narayana, Lattice Path Combinatorics with Statistical Applications, University of Toronto Press, coll. « Mathematical Expositions » (n^o 23), 1959, 104 p. (ISBN 978-0-8020-5405-0).
• Germain Kreweras, « Sur les partitions non croisées d'un cycle », Discrete Mathematics, vol. 1, n^o 4,‎ 1972, p. 333–350.
• Germain Kreweras, « Sur les éventails de segments », Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, n^o 15,‎ 1970, p. 3-41.
• Vladimir P. Kostov, Andrei Martínez-Finkelshtein et Boris Z. Shapiro, « Narayana numbers and Schur-Szegö composition », Journal of Approximation Theory, vol. 161, n^o 2,‎ 2009, p. 464-476 (DOI 10.1016/j.jat.2008.10.013, arXiv 0804.1028).
• J. Riordan, Combinatorial Identities, Wiley, 1968.
• Rodica Simion, « Noncrossing partitions », Discrete Mathematics, vol. 217, n^os 1–3,‎ 2000, p. 367–409.
• Robert A. Sulanke, « The Narayana distribution », Journal of Statistical Planning and Inference, vol. 101, n^os 1–2,‎ février 2002, p. 311-326.