Triangle de Catalan

En mathématiques et plus précisément en combinatoire, le triangle de Catalan est un tableau triangulaire de nombres dont les termes, notés $C(n,p)$, donnent le nombre de mots constitués de Modèle:Mvar lettres Modèle:Mvar et Modèle:Mvar lettres Modèle:Mvar, tels que tout segment initial possède plus ou autant de lettres Modèle:Mvar que de lettres Modèle:Mvar. Lorsque $n=p$, un tel mot est appelé un mot de Dyck, dont le nombre $C(n,n)$ est le nombre de Catalan d'indice Modèle:Mvar, d'où le fait que ce triangle porte le nom d'Eugène Charles Catalan.

Ce triangle est aussi en lien avec le problème du scrutin.

La première apparition des termes du triangle de Catalan définis par récurrence se trouve à la page 214 du traité publié en 1800 par Louis François Antoine Arbogast .

Shapiro a appelé « triangle de Catalan » un autre triangle, distinct de celui-ci, voir la Modèle:OEIS, et l'appellation « triangle de Catalan » est aussi donnée au triangle de Narayana.

Exemple

Lorsque nous parcourons un mot de Dyck ayant Modèle:Mvar lettres Modèle:Mvar et Modèle:Mvar lettres Modèle:Mvar de gauche à droite, le nombre de Modèle:Mvar rencontrés est toujours supérieur ou égal au nombre de Modèle:Mvar. Par exemple, les mots de Dyck pour

$n=3,p=2$

sont :

$XXXYY,XXYXY,XYXXY,XXYYX,XYXYX$ (3 terminés par Modèle:Mvar et 2 par Modèle:Mvar).

Par conséquent Modèle:Mvar(3,2) = 5.

Autres interprétations combinatoires

$C(n,p)$ est le nombre de jeux de pile ou face ayant obtenu Modèle:Mvar piles et Modèle:Mvar faces, tels que lors du déroulement du jeu le nombre de piles est resté constamment supérieur ou égal à celui du nombre de faces.

C'est aussi le nombre de dépouillements d'un scrutin à deux candidats ayant obtenus respectivement Modèle:Mvar et Modèle:Mvar voies tels que lors du dépouillement le premier candidat a constamment un nombre de voies supérieur ou égal à celui de son concurrent (problème du scrutin au sens large).

C'est encore le nombre de chemin dans ${\mathbb{N}}^2$ allant de $(0,0)$ à $(n,p)$ par déplacements vers la droite ou vers le haut se situant constamment au sens large au-dessous de la première bissectrice (la lettre Modèle:Mvar correspondant à l’ajout de (1, 0), et la lettre Modèle:Mvar à l'ajout de (0, 1)).

Définition par récurrence

Relations

Bailey a montré que les $C(n,p)$ sont définis par récurrence pour $0⩽p⩽n+1$ par les relations suivantes :

1. $C(n,0)=1\text{ pour }n⩾0$ .
2. $C(n,n+1)=0\text{ pour }n⩾0$ .
3. $C(n,p)=C(n,p-1)+C(n-1,p)\text{ pour }1⩽p⩽n$ .

La relation 3 exprime le fait que chaque terme du triangle est la somme du nombre à sa gauche et du nombre situé au-dessus de lui.

Construction du triangle

Voici le début du triangle, voir la Modèle:OEIS.

Modèle:Séparateur diagonal	0	1	2	3	4	5	6	7	8
0	1	0
1	1	1	0
2	1	2	2	0
3	1	3	5	5	0
4	1	4	9	14	14	0
5	1	5	14	28	42	42	0
6	1	6	20	48	90	132	132	0
7	1	7	27	75	165	297	429	429	0
8	1	8	35	110	275	572	1001	1430	1430

Démonstration des relations

• $C(n,0)=1$ pour $n⩾0$ car un seul mot ne contient pas la lettre Modèle:Mvar.
• $C(n,n+1)=0$ car le mot final ne peut avoir plus de lettres Modèle:Mvar que de lettres Modèle:Mvar.
• Un mot de Dyck ayant Modèle:Mvar Modèle:Mvar et Modèle:Mvar Modèle:Mvar se termine soit par Modèle:Mvar, soit par Modèle:Mvar. Dans le premier cas, il est formé d'un mot de Dyck à Modèle:Mvar – 1 Modèle:Mvar et Modèle:Mvar Modèle:Mvar, et dans le deuxième d'un mot de Dyck à Modèle:Mvar Modèle:Mvar et Modèle:Mvar – 1 Modèle:Mvar. Donc $C(n,p)=C(n,p-1)+C(n-1,p)$.

Autre définition par récurrence forte

Les $C(n,p)$ sont aussi définis pour $0⩽p⩽n$ par les relations suivantes, découlant des précédentes :

1. $C(0,0)=1$ .
2. $C(n,n+1)=0\text{ pour }n⩾0$.
3. $C(n,p)=\sum _{k=0}^{p}C(n-1,k)\text{ pour }0⩽p⩽n,n⩾1$ .

Ceci permet un remplissage simple du tableau ligne par ligne.

Formule générale

La formule générale de $C(n,p)$ pour $0⩽p⩽n+1$ est donnée parModèle:, :

$C(n,p)=\left(\begin{array}{c}n+p\\ p\end{array}\right)-\left(\begin{array}{c}n+p\\ p-1\end{array}\right)=(\genfrac{}{}{0ex}{}{n+p}{n})-(\genfrac{}{}{0ex}{}{n+p}{n+1})$,

soit $C(n,p)=\frac{(n+p)!(n-p+1)}{p!(n+1)!}=(\genfrac{}{}{0ex}{}{n+p}{p})\frac{(n-p+1)}{(n+1)}$.

La dernière formule montre que lors d'un scrutin à deux candidats, la probabilité que le vainqueur (à Modèle:Mvar bulletins) soit toujours en tête lors du dépouillement, ou à égalité avec le perdant (à Modèle:Mvar bulletins), vaut $\frac{(n-p+1)}{(n+1)}$.

Le terme diagonal $C(n,n)=\frac{(\genfrac{}{}{0ex}{}{2n}{n})}{n+1}$ est le [[nombre de Catalan|nombre de Catalan d'indice Modèle:Mvar]].

La somme des termes de la ligne d'indice Modèle:Mvar est égale, comme vu ci-dessus, à $C(n+1,n)$, lui-même égal à $C(n+1,n+1)$, nombre de Catalan d'indice Modèle:Formule.

Autre présentation du triangle

Le nombre de mots de Dyck à Modèle:Mvar lettres ayant Modèle:Mvar lettres Modèle:Mvar (donc Modèle:Mvar lettres Modèle:Mvar) vaut $D(n,p)=C(p,n-p)=(\genfrac{}{}{0ex}{}{n}{p})-(\genfrac{}{}{0ex}{}{n}{p+1})$.

Les nombres $D(n,p)$, strictement positifs pour $n/2⩽p⩽n$, sont alors définis par :

1. $D(n,n)=1\text{ pour }n⩾0$ .
2. $D(2n+1,n)=0\text{ pour }n⩾0$ .
3. $D(n,p)=D(n-1,p-1)+D(n-1,p)\text{ pour }n/2⩽p⩽n$ .

La dernière relation est la relation de Pascal.

Les premières valeurs sont :

Modèle:Séparateur diagonal	0	1	2	3	4	5	6	7	8
0	1	1
1	0	1
2		1	1
3		0	2	1
4			2	3	1
5			0	5	4	1
6				5	9	5	1
7				0	14	14	6	1
8					14	28	20	7	1

Sans les 0, il constitue la Modèle:OEIS.

Tableau d'Argobast

Louis Argobast a proposé en 1800 la récurrence définie par :

1. $A(0,p)=1\text{ pour }p⩾0$ .
2. $A(n,-1)=0\text{ pour }n⩾1$ .
3. $A(n,p)=A(n,p-1)+A(n-1,p+1)\text{ pour }n⩾1$ .

Selon ses termes, « chaque terme est formé de la somme de celui qui le précède dans la même ligne horizontale et de celui qui le suit d'un rang dans la ligne horizontale immédiatement supérieure », ce qui donne :

Modèle:Séparateur diagonal	-1	0	1	2	3	4	5	6	7	8
0		1	1	1	1	1	1	1	1	1
1	0	1	2	3	4	5	6	7	8	etc.
2	0	2	5	9	14	20	27	35	etc.
3	0	5	14	28	48	75	110	etc.
4	0	14	42	90	165	275	etc.
5	0	42	132	297	572	etc.
6	0	132	429	1001	etc.
7	0	429	1430	etc.
8	0	1430	etc.
9	0	etc.

Ce tableau reprend en les transposant les colonnes formées des termes non nuls du triangle de Catalan, ce qui se traduit par la relation $A(n,p)=C(n+p,n)=(\genfrac{}{}{0ex}{}{n+2p}{n})-(\genfrac{}{}{0ex}{}{n+2p}{n-1})$.

Les nombres de Catalan apparaissent cette fois dans la colonne d'indice 0 (ainsi que la colonne d'indice 1, décalés d'une position vers la ligne précédente, selon la Modèle:3e formule de récurrence, puisque la colonne d'indice -1 ne contient que des zéros).

Voir aussi

Articles connexes

• Nombre de Catalan
• Problème du scrutin
• Tableau triangulaire