Aller au contenu

Triangle de Catalan

Un article de Wikipédia, l'encyclopédie libre.

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 , donnent le nombre de mots constitués de n lettres X et p lettres Y, tels que tout segment initial possède plus ou autant de lettres X que de lettres Y. Lorsque , un tel mot est appelé un mot de Dyck, dont le nombre est le nombre de Catalan d'indice n, 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[1] par Louis François Antoine Arbogast .

Shapiro[2] a appelé « triangle de Catalan » un autre triangle, distinct de celui-ci, voir la suite A039598 de l'OEIS, et l'appellation « triangle de Catalan » est aussi donnée au triangle de Narayana.

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 sont :

(3 terminés par Y et 2 par X).

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

Autres interprétations combinatoires

[modifier | modifier le code]

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 allant de à 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)).

Définition par récurrence

[modifier | modifier le code]

Bailey[3] a montré que les sont définis par récurrence pour par les relations suivantes :

  1. .
  2. .
  3. .

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

[modifier | modifier le code]

Voici le début du triangle, voir la suite A009766 de l'OEIS.

p
n
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

[modifier | modifier le code]
  • pour car un seul mot ne contient pas la lettre Y.
  • car le mot final ne peut avoir plus de lettres Y que de lettres X.
  • Un mot de Dyck ayant n X et p Y se termine soit par X, soit par Y. Dans le premier cas, il est formé d'un mot de Dyck à n – 1 X et p Y, et dans le deuxième d'un mot de Dyck à n X et p – 1 Y. Donc .

Autre définition par récurrence forte

[modifier | modifier le code]

Les sont aussi définis pour par les relations suivantes, découlant des précédentes :

  1. .
  2. .
  3. .

Ceci permet un remplissage simple du tableau ligne par ligne.

Formule générale

[modifier | modifier le code]

La formule générale de pour est donnée par[3],[4] :

,

soit .

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 .

Le terme diagonal est le nombre de Catalan d'indice n.

La somme des termes de la ligne d'indice n est égale, comme vu ci-dessus, à , lui-même égal à , nombre de Catalan d'indice n + 1.

Autre présentation du triangle

[modifier | modifier le code]

Le nombre de mots de Dyck à n lettres ayant p lettres X (donc n - p lettres Y) vaut .

Les nombres , strictement positifs pour , sont alors définis par :

  1. .
  2. .
  3. .

La dernière relation est la relation de Pascal.

Les premières valeurs sont :

p
n
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 suite A008313 de l'OEIS.

Tableau d'Argobast

[modifier | modifier le code]

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

  1. .
  2. .
  3. .

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 :

p
n
-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 .

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 3e formule de récurrence, puisque la colonne d'indice -1 ne contient que des zéros).

Notes et références

[modifier | modifier le code]
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Catalan's triangle » (voir la liste des auteurs).
  1. a et b L. F. A. Arbogast, Du calcul des dérivations, (lire en ligne), p. 214.
  2. L. W. Shapiro, « A Catalan Triangle », Discrete Mathematics, vol. 14, no 1,‎ , p. 83-90 (DOI 10.1016/0012-365x(76)90009-1).
  3. a et b (en) D. F. Bailey, « Counting Arrangements of 1's and -1's », Mathematics Magazine, vol. 69, no 2,‎ , p. 128-131 (DOI 10.1080/0025570X.1996.11996408).
  4. Eric W. Weisstein, « Catalan's Triangle », MathWorld − A Wolfram Web Resource (consulté le ).

Articles connexes

[modifier | modifier le code]