Nombre de Narayana

Modèle:Voir homonymes En combinatoire, les nombres de Narayana $N (n, k)$ , pour $n = 1, 2, 3, \dots$ et $1 ⩽ k ⩽ n$ forment un tableau triangulaire d'entiers naturels, appelé triangle de Narayana ou triangle de Catalan. Ces nombres interviennent dans divers problèmes de dénombrements. Ils portent le nom de Tadepalli Venkata Narayana (1930-1987)^[1], mathématicien indo-canadien^[2].

Ils ne doivent pas être confondus avec les termes de la suite de Narayana, portant le nom d'un autre Naranaya.

Définition

Les nombres de Narayana s'expriment en fonction des coefficients binomiaux par la relation :

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

On trouve aussi la définition équivalente :

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

Les premiers nombres du triangle de Narayana sont les suivants :

n\k	1	2	3	4	5	6	7	8
1	1
2	1	1
3	1	3	1
4	1	6	6	1
5	1	10	20	10	1
6	1	15	50	50	15	1
7	1	21	105	175	105	21	1
8	1	28	196	490	490	196	28	1

Ils forment la Modèle:OEIS. La somme des nombres d'une ligne du triangle est un nombre de Catalan :

N (n, 1) + N (n, 2) + N (n, 3) + \dots + N (n, n) = C_{n} .

Interprétations combinatoires

Parenthésages

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

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

On voit facilement que $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, $N (n, n) = 1$ , le seul parenthésage possible est ()() ... (). Plus généralement, on peut prouver que le triangle de Narayana est symétrique, c'est-à-dire que $N (n, k) = N (n, n - k + 1)$

Si l'on représente un parenthésage par un chemin de Dyck, le nombre $N (n, k)$ compte les chemins de Dyck de longueur $2 n$ qui ont exactement $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 $N (4, k)$ :

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

Partitions non croisées

Modèle:Article détaillé

On considère un ensemble $S$ à $n$ éléments qui est ordonné de manière cyclique comme les sommets d'un polygone. Une partition de $S$ est non croisée (dans la terminologie de Modèle:Harvsp) si deux parties de la partition ne peuvent pas se croiser au sens suivant : si $a$ et $b$ appartiennent à un bloc et $x$ et $y$ à un autre bloc, ils ne sont pas rangés dans l'ordre $a x b y$ . En d'autres termes, si l'on trace des arcs reliant $a$ et $b$ d'une part, $x$ et $y$ d'autre part, ils ne doivent pas se croiser : ils se croisent si l'ordre est $a x b y$ , mais ne se croisent pas si l'ordre est $a x y b$ ou $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 à $n$ éléments est le nombre de Catalan $C_{n}$ . Le nombre de ces partitions non croisées comportant exactement $k$ blocs est le nombre de Narayana $N (n, k)$ .

Polyominos

Les polyominos parallélogrammes de périmètre $2 n$ 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 $n$ respectivement). Les polyominos parallélogrammes de périmètre $2 n + 2$ sont en bijection avec les chemins de Dyck de longueur $2 n$ , et les polyominos parallélogrammes de périmètre $2 n + 2$ qui ont $k$ colonnes sont comptés par les nombres de Narayana $N (n, k)$ ^[3].

Série génératrice

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

\frac{1}{2 x} (1 - x (1 + y) - \sqrt{(1 - x (1 + y))^{2} - 4 y x^{2}}) = \sum_{n > 0, k > 0} N (n, k) x^{n} y^{k}

.

Polynômes de Narayana

Modèle:Article détaillé Les polynômes de Narayana sont les fonctions génératrices des lignes du triangle de Narayana, définis par la formule

N_{n} (x) = \sum_{k = 1}^{n} N (n, k) x^{k}

.

Ces polynômes satisfont à la relation de récurrence suivante^[5] :

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

avec $N_{1} (x) = x$ et $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].

Bien sûr, vu les interprétations combinatoires précédentes, la valeur du polynôme de Narayana N_n en 1 est $N_{n} (1) = C_{n}$ , le n-ième nombre de Catalan.

Pages liées

Notes et références

Notes

Modèle:Références Modèle:Traduction/Référence

Références

Modèle:Portail

↑ Modèle:Harvsp
↑ C'est Modèle:Harvsp qui leur attribue ce nom. Riordan, dans son traité Modèle:Harvsp, les nomme nombres de Runyon « for my colleague John P. Runyon who encountered these numbers in telephone traffic problem ». Cette information est de Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Modèle:OEIS.
↑ Modèle:Harvsp.
↑ Modèle:Harvsp.

[1] Modèle:Harvsp

[2] C'est Modèle:Harvsp qui leur attribue ce nom. Riordan, dans son traité Modèle:Harvsp, les nomme nombres de Runyon « for my colleague John P. Runyon who encountered these numbers in telephone traffic problem ». Cette information est de Modèle:Harvsp.

[3] Modèle:Harvsp.

[4] Modèle:OEIS.

[5] Modèle:Harvsp.

[6] Modèle:Harvsp.

[1]

[2]

[3]

[4]

[5]

[6]

Nombre de Narayana

Sommaire

Définition