Considère ces deux problèmes. Premier : avec n parenthèses ouvrantes « ( » et n parenthèses fermantes « ) », de combien de façons peut-on les ranger pour qu'à aucun moment il n'y ait plus de fermantes que d'ouvrantes ? Second : de combien de façons peut-on découper un polygone convexe à (n+2) côtés avec des diagonales pour que chaque morceau soit un triangle ? Ces problèmes semblent n'avoir aucun rapport, et pourtant, chose remarquable, la réponse aux deux est exactement la même suite : 1, 1, 2, 5, 14, 42, 132… Ces nombres s'appellent les nombres de Catalan.

Les nombres de Catalan sont donnés par la formule Cn = (2n)! / ((n+1)! × n!). En remplaçant n par 0, 1, 2…, on obtient C0=1, C1=1, C2=2, C3=5, C4=14, C5=42, et ainsi de suite. Par exemple, les rangements valides avec 3 paires de parenthèses sont ((())), (()()), (())(), ()(()) et ()()() : il y en a exactement 5.

Or, compte les façons de découper un pentagone (polygone à 5 côtés) en triangles avec des diagonales, et tu obtiens aussi exactement 5. Ce n'est pas un hasard. Un pentagone se découpe en 3 triangles avec 2 diagonales, et comme c'est un polygone à (n+2) côtés avec n=3, cela correspond exactement à C3=5. Le problème des parenthèses et celui du polygone partagent la même structure de fond : « le nombre de façons de couper récursivement quelque chose en deux morceaux ».

Il y a 5 façons de découper un pentagone en 3 triangles avec 2 diagonales, exactement autant que de façons d'apparier 3 paires de parenthèses

Les mathématiciens décrivent cette coïncidence apparente en disant qu'« il existe une bijection » entre les deux problèmes : les réponses des deux problèmes peuvent être associées une à une. Si l'on fait correspondre chaque parenthèse à une diagonale du polygone, et l'emboîtement des parenthèses à l'ordre dans lequel les triangles s'accrochent, les deux problèmes se traduisent exactement l'un dans l'autre. Même 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 ce même Cn.

Les nombres de Catalan portent le nom du mathématicien belge Eugène Catalan, mais ils avaient en fait été étudiés plus tôt, et indépendamment, par le Suisse Leonhard Euler et le Mongol Minggatu. Ces nombres apparaissent dans plus de 200 problèmes de combinatoire connus, cachés dans toutes sortes de recoins des mathématiques.

Sur notre page d'activité, tu peux changer n et voir exactement comment chaque nombre de Catalan se calcule, et afficher tous les rangements valides de parenthèses pour les compter de tes propres yeux. Tu peux aussi parcourir une à une toutes les triangulations d'un polygone pour vérifier toi-même que les réponses des deux problèmes grandissent vraiment exactement de la même façon.