Triangle de Catalan

Lorsque nous parcourons un mot de Dyck ayant n lettres X et p lettres Y de gauche à droite, le nombre de X rencontrés est toujours supérieur ou égal au nombre de Y. Par exemple, les mots de Dyck pour ${\displaystyle n=3,p=2}$ sont :

${\displaystyle XXXYY,\quad XXYXY,\quad XYXXY,\quad XXYYX,\quad XYXYX}$ (3 terminés par Y et 2 par X).

Par conséquent C(3,2) = 5.

${\displaystyle C(n,p)}$ est le nombre de jeux de pile ou face ayant obtenu n piles et p 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 n et p 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 ${\displaystyle \mathbb {N} ^{2}}$ allant de ${\displaystyle (0,0)}$ à ${\displaystyle (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 X correspondant à l’ajout de (1, 0), et la lettre Y à l'ajout de (0, 1)).

La formule générale de ${\displaystyle C(n,p)}$ pour ${\displaystyle 0\leqslant p\leqslant n+1}$ est donnée par[3] - [4] :

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

soit ${\displaystyle C(n,p)={\frac {(n+p)!(n-p+1)}{p!(n+1)!}}={\binom {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 (à n bulletins) soit toujours en tête lors du dépouillement, ou à égalité avec le perdant (à p bulletins), vaut ${\displaystyle {\frac {(n-p+1)}{(n+1)}}}$.

Le terme diagonal ${\displaystyle C(n,n)={\frac {\binom {2n}{n}}{n+1}}}$ est le nombre de Catalan d'indice n.

La somme des termes de la ligne d'indice n est égale, comme vu ci-dessus, à ${\displaystyle C(n+1,n)}$, lui-même égal à ${\displaystyle C(n+1,n+1)}$, nombre de Catalan d'indice n + 1.

Le nombre de mots de Dyck à n lettres ayant p lettres X (donc n - p lettres Y) vaut ${\displaystyle D(n,p)=C(p,n-p)={\binom {n}{p}}-{\binom {n}{p+1}}}$.

Les nombres ${\displaystyle D(n,p)}$, strictement positifs pour ${\displaystyle n/2\leqslant p\leqslant n}$, sont alors définis par :

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

La dernière relation étant la relation de Pascal.

Les premières valeurs sont :

Sans les 0, il constitue la suite A008313 de l'OEIS.

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

1. ${\displaystyle A(0,p)=1{\text{ pour }}p\geqslant 0}$ .
2. ${\displaystyle A(n,-1)=0{\text{ pour }}n\geqslant 1}$ .
3. ${\displaystyle A(n,p)=A(n,p-1)+A(n-1,p+1){\text{ pour }}n\geqslant 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 :

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 ${\displaystyle A(n,p)=C(n+p,n)={\binom {n+2p}{n}}-{\binom {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 3^e formule de récurrence, puisque la colonne d'indice -1 ne contient que des zéros).