Présentation

• Ce sujet est organisé en trois parties largement indépendants. La première établit, par des moyens élémentaires, l'expression simple du n-ième nombre de Catalan.
• La deuxième partie s'intéresse au langage de Dyck, et montre que le nombre de mots de longueur 2n de ce langage est justement le n-ième nombre de Catalan.
• Dans la troisième partie, on s'intéresse aux diverses façons de calculer le produit de n matrices. On montre que le nombre de façons est justement le n-ième nombre de Catalan. On propose ensuite un algorithme pour obtenir un ordonnancement des calculs minimisant le nombre d'opérations effectuées.