Dyck word

Imaginez une réserve qui gagne une unité à chaque X et en perd une à chaque Y. Le mot XXYXYY fait ainsi évoluer la réserve de 0 à 1, 2, 1, 2, 1, puis 0. Elle ne devient jamais négative et revient à zéro : ce mot est un mot de Dyck.

Les deux règles se lisent donc directement : autant de X que de Y au total, et jamais davantage de Y que de X dans ce qui a déjà été lu.

Un mot de Dyck est une suite finie écrite avec les deux lettres X et Y. Pour un entier n au moins égal à 1, sa longueur est 2n : il contient exactement n lettres X et n lettres Y. De plus, chacun de ses préfixes contient au moins autant de X que de Y. Un préfixe est la portion initiale formée par les k premières lettres, pour une valeur de k comprise entre 1 et 2n.

On peut suivre la différence entre le nombre de X et le nombre de Y après chaque lettre. Cette différence reste positive ou nulle, puis vaut zéro à la fin. Pour XXYXYY, elle prend successivement les valeurs 1, 2, 1, 2, 1 et 0. Cette lecture rend visible la condition sur tous les préfixes.

Le résultat du dénombrement des mots de Dyck de longueur 2n est le n-ième nombre de Catalan, noté C_n. Il se calcule par la formule $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0px}{}{2n}{n}\right)C\_n=\backslash frac\{1\}\{n+1\}\backslash binom\{2n\}\{n\}$, où le coefficient binomial compte les choix de n positions parmi 2n. Pour n égal à 3, cette formule donne C₃ = 5.

On veut vérifier le mot XXYXYY. Les données sont ses six lettres, trois X et trois Y. On associe +1 à X et −1 à Y, puis on part de 0.

1. Après le premier X, le total vaut 1.
2. Après le deuxième X, il vaut 2.
3. Après Y, il redescend à 1.
4. Après X, il remonte à 2.
5. Après Y, puis le dernier Y, il vaut successivement 1 et 0.

Le total n'est négatif à aucune étape et finit à 0. Le mot XXYXYY est donc un mot de Dyck de longueur 6. Pour contrôler le résultat, il suffit de recompter trois X et trois Y, puis de relire la suite des totaux : 1, 2, 1, 2, 1, 0.

Pour tester un mot donné, on tient un compteur : +1 pour X et −1 pour Y. Dès que le compteur devient négatif, un préfixe contient trop de Y et le mot est rejeté. S'il reste non négatif et termine à 0, le mot est accepté.

Pour dresser la liste à une longueur fixée, on peut examiner les suites contenant autant de X que de Y, puis écarter celles dont un préfixe échoue. Pour connaître seulement le nombre de mots, la formule du nombre de Catalan évite cette énumération.

Une représentation par montées et descentes permet aussi de contrôler la lecture : X fait monter d'une unité et Y fait descendre d'une unité. Le tracé convient lorsque l'on veut voir immédiatement le premier éventuel passage sous le niveau de départ.

Mot de Dyck et nombre de Catalan. Un mot de Dyck est une suite particulière de X et de Y ; un nombre de Catalan compte tous les mots de Dyck d'une longueur donnée. Ainsi, XXYXYY est un mot, tandis que 5 est le nombre de ces mots lorsque n vaut 3.

Mot de Dyck et chemin de Dyck. Le premier est la suite de lettres ; le second est sa représentation par pas montants et descendants. XXYXYY et son tracé portent la même succession de choix, mais l'un se lit comme un mot et l'autre comme un chemin.

L'égalité finale ne suffit pas. Le mot YXXXYY contient trois X et trois Y, mais son premier préfixe contient déjà plus de Y que de X. Le compteur vaut −1 dès la première lettre : il faut donc contrôler chaque préfixe, pas seulement le total.

Le seuil est zéro. Un compteur égal à zéro au milieu du mot est autorisé ; il indique seulement qu'un préfixe contient autant de X que de Y. En revanche, une seule valeur strictement négative suffit à exclure le mot.

La convention commence ici à n = 1. La définition source exclut donc le mot vide, qui correspondrait à n = 0 dans une convention élargie. Pour cette fiche, la plus petite longueur admise est 2, et XY est l'unique cas à cette longueur.

Le nombre de Catalan prolonge le comptage des mots de Dyck et détaille la suite à laquelle appartient la valeur C₃ = 5.

L'analyse combinatoire replace cette énumération parmi les méthodes qui organisent et comptent des configurations finies.