mot de Dyck

COMBINATOIRE

Un mot de Dyck est une chaîne de caractères formée de n lettres X et de n lettres Y, telle tout mot obtenu en supprimant les dernières lettres à partir d’un rang quelconque ne contienne pas plus de Y que de X.
Par exemple, les mots de Dyck de longueur 6 sont XXXYYY, XYXXYY, XYXYXY, XXYYXY, XXYXYY. Il sont au nombre de 5 qui est le nombre de Catalan C3 :
D’une façon générale, le nombre de mots de Dick de longueur 2n est le n-ième nombre de Catalan Cn