Le nombre de façons d'apparier des parenthèses et le nombre de façons de découper un polygone en triangles avec des diagonales semblent sans aucun rapport au premier coup d'œil. Et pourtant, chose remarquable, les deux donnent exactement la même suite (1, 1, 2, 5, 14, 42...). Ces nombres fascinants s'appellent les nombres de Catalan.
Les nombres de Catalan sont donnés par la formule Cn = (2n)! / ((n+1)! × n!). À partir de n=0, ils valent 1, 1, 2, 5, 14, 42, 132... Change n ci-dessous pour voir les valeurs, et énumère toi-même les cas pour comprendre pourquoi apparier des parenthèses et trianguler un polygone donnent exactement le même nombre.
Choisis n et vois exactement comment se calcule le nombre de Catalan.
Avec n paires de parenthèses ouvrantes et fermantes, énumère tous les rangements où les parenthèses s'apparient correctement (à aucun moment il n'y a plus de fermantes que d'ouvrantes).
Vois de combien de façons on peut découper un polygone à (n+2) côtés avec des diagonales pour que chaque morceau soit un triangle, en les parcourant une à une.
Le nombre de formes différentes d'un arbre binaire à n nœuds (une structure d'arbre où chaque nœud a au plus un enfant gauche et un enfant droit) vaut lui aussi exactement le nombre de Catalan Cn. Si l'on voit chaque parenthèse comme un nœud et l'emboîtement des parenthèses comme les branches d'un arbre, on s'aperçoit que les trois problèmes (parenthèses, polygones, arbres binaires) sont en réalité la même structure sous des habits différents.
Pour des problèmes comme ceux-ci, complètement différents en apparence mais qui comptent exactement la même chose, les mathématiciens disent qu'« il existe une bijection » entre eux. Les nombres de Catalan apparaissent dans plus de 200 problèmes de combinatoire connus.