Une même suite compte les parenthèses, les arbres et les triangulations

Pourquoi un analyseur ne peut pas tout essayer

Le nombre de façons de parenthéser une chaîne de multiplications est un nombre de Catalan, et il dépasse le milliard avant que la chaîne n'atteigne vingt termes. La multiplication matricielle est associative : tous les parenthésages donnent le même produit — mais ils ne coûtent pas tous pareil, et l'écart entre le meilleur et le pire ordre peut atteindre plusieurs ordres de grandeur d'opérations. Énumérer les possibilités pour trouver la moins chère est donc sans espoir au-delà d'une poignée de matrices, et la solution standard est la programmation dynamique, qui trouve l'optimum en temps cubique en ne résolvant jamais deux fois le même sous-problème. Le nombre de Catalan est ce que cet algorithme évite.

L'image des parenthèses explique toute la famille

Chacun de ces problèmes est une suite de pas qui ne doit jamais devenir négative. Lis une parenthèse ouvrante comme plus un et une fermante comme moins un : une chaîne valide est exactement une marche qui finit à zéro sans jamais passer dessous. Un arbre binaire parcouru dans l'ordre donne la même marche ; une triangulation aussi, et une file d'attente qui ne doit jamais servir un client non encore arrivé également. Le déguisement tombé, un seul argument de dénombrement les couvre tous, et la démonstration standard est une astuce de réflexion qui compte les mauvaises marches en les renvoyant dans un ensemble facile à compter.

Questions fréquentes

Pourquoi la suite commence-t-elle par deux uns ?

Parce qu'il y a exactement une façon de ne rien faire et exactement une façon de faire la plus petite chose possible. Avec zéro paire de parenthèses, la chaîne vide est le seul arrangement valide, et avec une paire il n'y a qu'un placement. Les suites qui comptent des arrangements commencent très souvent ainsi, et le un répété signale que la définition a été étendue sensément au cas vide au lieu de démarrer arbitrairement à la première valeur intéressante. Cela compte aussi au calcul : la récurrence a besoin des deux comme base avant de pouvoir engendrer quoi que ce soit.

À quelle vitesse ces nombres croissent-ils vraiment ?

Un peu moins de quatre fois par pas, et le rapport se rapproche lentement de quatre à mesure que n grandit : du dix-neuvième au vingtième terme il vaut 3,714, du vingt-neuvième au trentième 3,807. Cela les place entre la croissance exponentielle des puissances de deux et la croissance bien plus violente des factorielles — assez pour mettre en échec la force brute rapidement, pas assez pour la mettre en échec immédiatement. En pratique, la bascule se situe autour de vingt : en dessous, une recherche exhaustive passe souvent, au-dessus il faut quelque chose de plus fin, et le point exact dépend du coût de chaque cas.