Résoudre des équations en comptant des arbres

Piste bleue Le 13 octobre 2018  - Ecrit par  Nils Berglund Voir les commentaires (2)

Résoudre certaines équations polynomiales est équivalent à compter des arbres d’un type particulier. Nous verrons pourquoi c’est vrai, comment faire pour dénombrer ces arbres, et quel est l’intérêt d’une telle approche.

Remarque : la piste devient rouge vers la fin... (NDLR).

Une équation linéaire [1]

Nous allons nous intéresser à des équations dépendant d’un paramètre, comme par exemple
\[ (1-a) x = 1 \]
Ici le nombre réel $x$ est l’inconnue, alors que $a$ est un nombre réel pouvant varier, appelé paramètre. Le but est de déterminer la valeur de l’inconnue $x$ pour différentes valeurs du paramètre $a$. Pour que l’équation ait un sens, on supposera ici que $a$ est différent de $1$.

Notre exemple est assez simple pour pouvoir être résolu directement, puisqu’on a
\[ x = \frac{1}{1-a} \]
Par exemple, si nous remplaçons $a$ par $0,\!01$, nous obtenons
\[ x = \frac{1}{0,\!99} = 1,\!01010101 \dots \]
On peut remarquer la répétition périodique des décimales. C’est bien sûr une caractéristique de tous les nombres rationnels, mais cela cache aussi une autre particularité de notre équation. Amusez-vous à remplacer $a$ par $0,\!001$ ou par $0,\!02$. Qu’observez-vous ?

Nous aurions pu procéder autrement, et écrire l’équation sous la forme
\[ x = 1 + a x \]
Comme l’inconnue $x$ apparaît des deux côtés du signe égal, ceci ne résout en rien l’équation. Cependant, si nous remplaçons le $x$ de droite par $1+ax$ (ce qui est permis, puisque ces deux quantités sont égales), cela donne
\[ x = 1 + a (1 + ax) = 1 + a + a^2x \]
En répétant l’opération de remplacement de $x$ par $1+ax$ à droite du signe égal, on trouve [2]
\[ x = 1 + a + a^2 + a^3x \]
En continuant de cette manière, on voir apparaître les puissances successives de $a$, mais il restera toujours en dernier un « terme de reste » de la forme $a^nx$ pour un entier positif $n$. On peut toutefois se demander si ce reste peut être négligé lorsque $n$ devient de plus en plus grand, de sorte qu’on aurait l’égalité
\[ \frac{1}{1-a} = 1 + a + a^2 + a^3 + \dots \]
où on sous-entend qu’il y a une infinité de termes à droite du signe égal. Un résultat important du domaine de l’analyse, la convergence de la série géométrique, affirme que c’est vrai à condition que $-1 < a < 1$ [3].
Nous n’allons pas développer ce résultat, qui est détaillé par exemple ici sur Images des Mathématiques. En voici toutefois une illustration géométrique lorsque $a=\frac12$, directement inspirée d’une image vue sur le site de l’ICM 2018 :

Voyez-vous pourquoi ce dessin montre que l’on a bien
\[ 2 = 1 + \frac12 + \frac14 + \frac18 + \frac1{16} + \dots + \frac1{2^n} + \dots \qquad ? \]
On trouvera ici et d’autres preuves géométriques de cette égalité, aussi pour d’autres valeurs de $a$.

Une équation du second degré

Intéressons-nous maintenant à l’équation
\[ ax^2 - x + 1 = 0 \]
Il s’agit encore une fois d’une équation que l’on sait résoudre explicitement, mais sa solution ne jouera pas de rôle important dans la suite. Dans un souci de complétude, celle-ci est toutefois décrite dans le bloc dépliant suivant.

Équations du second degré

Pour $a$ un nombre réel non nul, et $b$ et $c$ deux nombres réels quelconques, considérons l’équation
\[ a x^2 + b x + c = 0 \]
Celle-ci est équivalente à
\[ a \left( x + \frac{b}{2a} \right)^2 - \frac{b^2}{4a} + c = 0 \]
ou encore
\[ \left( x + \frac{b}{2a} \right)^2 = \frac{b^2 - 4ac}{(2a)^2} \]
On appelle discriminant le nombre $\Delta = b^2 - 4 a c$. Il y a alors trois cas de figure :

  • Si $\Delta>0$, alors l’équation admet deux solutions, à savoir [4]
    \[ \frac{-b+\sqrt{\Delta}}{2a} \qquad\text{et}\qquad \frac{-b-\sqrt{\Delta}}{2a} \]
  • Si $\Delta=0$, alors l’équation admet une seule solution, à savoir $-\frac{b}{2a}$.
  • Si $\Delta<0$, alors l’équation n’admet pas de solution réelle (mais on peut définir des nombres complexes jouant le rôle de solutions).

Dans le cas de l’équation qui nous intéresse, nous avons $b=-1$ et $c=1$. Le discriminant vaut donc $\Delta = 1-4a$, et ce qui précède implique que si $a<\frac14$, l’équation admet deux solutions réelles données par
\[ \frac{1+\sqrt{1-4a}}{2a} \qquad\text{et}\qquad \frac{1-\sqrt{1-4a}}{2a} \]

Essayons d’appliquer la même approche que pour l’équation linéaire, en écrivant notre équation du second degré sous la forme
\[ x = 1 + a x^2 \]
Comme auparavant, l’inconnue $x$ apparaît des deux côtés du signe $=$. Nous pouvons toutefois remplacer $x$ par $1+ax^2$ à droite, ce qui donne
\[ x = 1 + a (1+ax^2)^2 = 1 + a + 2 a^2 x^2 + a^3 x^4 \]
(où nous avons utilisé l’identité remarquable $(y+z)^2 = y^2 + 2yz + z^2$ pour développer le carré).

Nous pouvons alors répéter l’opération consistant à remplacer $x$ par $1+ax^2$ à droite de l’égalité. Contrairement au premier cas, toutefois, les calculs deviennent vite assez pénibles. Avec un peu de patience (ou un logiciel de calcul formel), on obtient après deux substitutions supplémentaires la relation
\[ x = 1 + a + 2 a^2 + 5 a^3 + 14 a^4 + \dots \]
dans laquelle les points de suspension indiquent des termes de degré $5$ ou plus en $a$, et pouvant dépendre de $x$. Si l’on prend $a=0,\!01$, ceci suggère que
\[ \begin{array}{rcl} x &=& 1 + 0,\!01 + 2\times(0,\!01)^2 + 5\times(0,\!01)^3 + 14\times(0,\!01)^4 + \dots \\ &=& 1,\!01020514\dots \end{array} \]
est une bonne approximation d’une solution de l’équation, ce que l’on peut effectivement vérifier à l’aide d’une calculette.

Se pose alors la question de savoir s’il y a un moyen plus simple d’obtenir la suite
\[ 1, 1, 2, 5, 14, \dots \]
de coefficients apparaissant dans l’expression de $x$.

Alerte au spoiler

Une méthode consiste à aller regarder sur l’Encyclopédie en Ligne des Suites d’Entiers, et de lui soumettre ces cinq nombres. Le site nous propose alors plusieurs solutions de suites infinies commençant par ces cinq nombres, que nous n’allons toutefois pas divulguer ici afin de préserver le suspense...

Une représentation graphique

Représentons l’équation $x=1+ax^2$ graphiquement, sous la forme

Le symbole à gauche de l’égalité, censé représenter une feuille, est notre inconnue $x$. Le petit arbuste à deux branches à droite de l’égalité correspond au terme $x^2$. Autrement dit, la multiplication de deux symboles est représentée en les joignant par deux branches.

Appliquons maintenant l’opération de substitution. Pour cela, nous devons remplacer chaque feuille de l’arbuste soit par $1$, soit par $ax^2$. Il y a donc quatre possibilités, qui donneront lieu à quatre termes :

  • Soit on remplace les deux feuilles par $1$, ce que nous représentons en enlevant les deux feuilles.
  • Soit on remplace la première feuille par $ax^2$ et la seconde par $1$. Cela se traduit en remplaçant la feuille de gauche par l’arbuste, en enlevant celle de droite, et en remplaçant le coefficient $a$ par $a^2$ afin de tenir compte du facteur $a$.
  • Soit on remplace, de manière analogue, la première feuille par $1$ et la seconde par $ax^2$.
  • Soit, enfin, on remplace les deux feuilles par $ax^2$, ce qui donne lieu à un nouveau coefficient $a^3$.

Le résultat est l’égalité

L’étape suivante consiste à remplacer à nouveau chaque feuille soit par $1$, soit par un arbuste à deux feuilles, en prenant soin d’incrémenter convenablement l’exposant de $a$. Par exemple, le second arbre dans la dernière équation devient

Procédant de même pour les autres arbres, on obtient une somme de $26$ termes, dont le degré en $a$ va jusqu’à $7$. Nous ne donnons ici que les termes de degré au plus $3$ en $a$, qui sont

Dans l’étape d’après, chaque feuille est à nouveau soit enlevée, soit remplacée par un arbuste à deux feuilles. Mais comme ces derniers termes seront de degré $4$ au moins en $a$, les termes jusqu’à l’ordre $3$ sont simplement ceux de l’équation précédente sans les feuilles :

Nous observons que dans cette expression, tous les arbres sont des arbres binaires, c’est-à-dire qu’à chaque embranchement il y a deux branches vers le haut et une vers le bas (sauf à la racine). De plus, il y a exactement [5]

  • $1$ arbre binaire à $2$ feuilles : ,
  • $2$ arbres binaires à $3$ feuilles : , ,
  • $5$ arbres binaires à $4$ feuilles : , , , , .

Il est commode de décréter qu’il existe également $1$ arbre binaire à $1$ feuille : c’est l’arbre sans branche , formé juste d’une feuille collée à la racine. On l’appellera l’arbre trivial.

À vous de vous convaincre qu’il n’existe pas d’autres arbres binaires à $2$, $3$ ou $4$ feuilles que ceux apparaissant dans notre développement, et qu’il existe en tout $14$ arbres binaires à $5$ feuilles. Autrement dit, nous avons fait l’observation suivante :

Observation

Pour tout entier $n\ge0$, le coefficient de $a^n$ dans l’expression de $x$ est égal au nombre d’arbres binaires à $n+1$ feuilles.

À vrai dire, nous n’avons montré cette observation que pour $n = 0,1,2,3$. Il faut un peu de réflexion pour se persuader du fait qu’elle reste vraie pour tout $n$... c’est une conséquence de la construction par substitutions successives. Nous avons ici un bel exemple d’abstraction mathématique : on n’a pas besoin de dessiner tous les arbres pour savoir qu’ils interviennent dans le développement.

Les nombres de Catalan

Notons $C_n$ le nombre d’arbres binaires à $n+1$ feuilles. On l’appelle le $n$ième nombre de Catalan, en l’honneur du mathématicien franco-belge Eugène Charles Catalan. Comme on peut le voir sur la page Wikipedia qui leur est dédiée, ces nombres interviennent dans une multitude de problèmes combinatoires [6].

Le tableau suivant regroupe les cinq premiers nombre de Catalan que nous avons rencontrés jusqu’ici :

$n$ $C_n$ Arbres binaires à $n+1$ feuilles
$0$ $1$
$1$ $1$
$2$ $2$
$3$ $5$
$4$ $14$ À vous de compléter...

La question naturelle qui se pose alors est : Peut-on obtenir une formule explicite permettant de calculer tous les nombres de Catalan ?

Une relation de récurrence

Un premier pas vers une formule explicite est d’établir une relation de récurrence entre les nombres de Catalan. Partons de l’observation suivante : Si l’on scie les deux branches issues de la racine d’un arbre binaire à $n+2$ feuilles, on obtient deux arbres binaires. Si le premier a $k+1$ feuilles, le second doit en avoir $n-k+1$.

Dit autrement, on peut fabriquer un arbre binaire à $n+2$ feuilles en greffant un arbre à $k+1$ feuilles et un arbre à $n-k+1$ feuilles sur la racine. Ici l’entier $k$ peut prendre n’importe quelle valeur entre $0$ et $n$.

Comme il y a $C_k$ choix pour le premier arbre, et $C_{n-k}$ choix pour le second, on aboutit à la relation de récurrence
\[ C_{n+1} = C_0 C_n + C_1 C_{n-1} + C_2 C_{n-2} + \dots + C_{n-1} C_1 + C_n C_0 \]
Par exemple, pour fabriquer un arbre à $3$ feuilles, on peut combiner, dans n’importe quel ordre, un arbre à $1$ feuille (arbre trivial) et un arbre à $2$ feuilles, d’où
\[ C_2 = C_0 C_1 + C_1 C_0 = 1 \times 1 + 1 \times 1 = 2 \]
Pour les deux nombres de Catalan suivants, on obtient
\[ \begin{array}{rcl} C_3 &=& C_0C_2 + C_1^2 + C_2C_0 = 2 + 1 + 2 = 5 \\ C_4 &=& C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0 = 5 + 2 + 2 + 5 = 14 \end{array} \]
Il est recommandé de retrouver les arbres correspondant à chaque terme de ces sommes !

Exercice

Calculer $C_5$, $C_6$ et $C_7$.

Réponse

\[ C_5 = C_0C_4 + C_1C_3 + C_2^2 + C_3C_1 + C_4C_0 = 14 + 5 + 4 + 5 + 14 = 42 \]
Les deux nombres de Catalan suivants sont $C_6 = 132$ et $C_7 = 429$.

Mots et chemins de Dyck

Si la relation de récurrence nous permet, en principe, de calculer n’importe quel nombre de Catalan, elle nous oblige à tous les calculer l’un après l’autre. Pour déterminer le centième nombre de Catalan, il faut avoir au préalable déterminé les $99$ nombres précédents, ce qui n’est pas très pratique. On préférerait disposer d’une méthode plus directe pour calculer les $C_n$ !

La branche des mathématiques dédiée à compter le nombre d’objets d’un certain type s’appelle la combinatoire énumérative. L’une de ses principales méthodes consiste à établir des bijections entre différents types d’objets mathématiques. Autrement dit, on remplace les objets que l’on souhaite dénombrer par d’autres objets, en nombre égal, et plus faciles à compter.

En l’occurrence, nous allons commencer par attribuer à chaque arbre binaire un mot, constitué uniquement des lettres $a$ et $b$. Ce mot est construit en partant des feuilles et en descendant vers la racine, à l’aide des deux règles suivantes :

  1. Aux feuilles de l’arbre on associe le mot vide.
  2. Si au-dessus d’un embranchement donné se trouvent les mots $\color{blue}{x}$ et $\color{blue}{y}$ (éventuellement vides), alors on lui associe le mot $a\color{blue}{x}b\color{blue}{y}$ :

Par exemple, tout embranchement situé directement en dessous de deux feuilles portera le mot $ab$. La figure suivante illustre ce procédé sur les $5$ arbres à $4$ feuilles.

Observons qu’on obtient toujours des mots de $6$ lettres, dont $3$ lettres $a$ et $3$ lettres $b$. Combien y a-t-il de tels mots ? C’est un problème de combinatoire bien compris, faisant intervenir le triangle de Pascal, comme expliqué notamment ici sur Images des Mathématiques. Le nombre de mots cherché est donné par le coefficient binomial
\[ \binom{6}{3} = \frac{6\times 5\times 4}{3\times 2\times 1} = 20 \]
Mais il n’existe que $5$, et pas $20$ arbres binaires à $4$ feuilles ! Pourquoi cette différence ?

L’explication est que tous les mots possibles ne sont pas produits par notre procédé. Par exemple, celui-ci produit toujours des mots commençant par la lettre $a$. Pour mieux comprendre ce qui se passe, nous allons introduire une seconde bijection qui associe à chaque mot une ligne en dents de scie, en remplaçant chaque $a$ par une diagonale montante, et chaque $b$ par une diagonale descendante [7]. Le résultat pour les mots associés aux arbres à $4$ feuilles est le suivant :

On observe que l’on n’obtient que des lignes brisées ne descendant pas en dessous de l’axe des abscisses. Ces lignes sont appelées chemins de Dyck en référence au mathématicien allemand Walther von Dyck. Les mots associés, appelés mots de Dyck, ont la particularité suivante : si on les coupe en deux morceaux de taille pas forcément égale, le morceau de gauche a toujours au moins autant de $a$ que de $b$.

Exercice

Montrer qu’il y a bien une bijection entre les arbres binaires et les mots de Dyck. Cela revient à vérifier deux choses : d’une part, que le procédé décrit ci-dessus associe à chaque arbre binaire un mot de Dyck ; et d’autre part, que chaque mot de Dyck provient bien d’un arbre binaire.

Indications

La première vérification est un peu plus facile, car il suffit de montrer que tous les mots associés aux différents embranchements d’un arbre binaire sont des mots de Dyck. Comme ceux-ci sont construits par récurrence, il suffit de vérifier que la procédure de récurrence transforme un mot de Dyck en un autre mot de Dyck (les mots vides associés aux feuilles étant des mots de Dyck « triviaux »).

La seconde vérification est un peu plus difficile. Le mieux est de trouver un procédé permettant de construire l’arbre binaire à partir du mot de Dyck. Une indication : il faut distinguer deux cas :

  • si le chemin de Dyck ne touche pas l’axe des abscisses entre ses extrémités (comme dans les deux premiers cas de la figure ci-dessus), on enlève la première et la dernière lettre du mot ; quelle est la relation entre l’arbre associé à ce mot et l’arbre de départ ?
  • si le chemin touche l’axe à une ou plusieurs reprises, il est composé de plusieurs chemins de Dyck plus petits ; quel lien y a-t-il entre les arbres associés au mot de Dyck de départ et aux mots plus petits ?

Compter les chemins de Dyck

Il nous reste à compter les chemins de Dyck de longueur $2n$ : cela nous donnera automatiquement le nombre $C_n$ d’arbres binaires à $n+1$ feuilles. Nous avons vu qu’il y a $20$ mots composés de $3$ lettres $a$ et $3$ lettres $b$. Nous pouvons leur associer $20$ chemins en dent de scie, partant de la hauteur $0$ et y revenant, mais pouvant passer en dessous de l’axe des abscisses. Appelons-les des excursions.

Nous avons aussi vu que parmi ces $20$ excursions de longueur $6$, seulement $5$ sont des chemins de Dyck. Ceci suggère qu’à chaque chemin de Dyck, on peut associer exactement $3$ excursions qui passent en dessous de l’axe. Comment caractériser ces $3$ excursions ?

L’idée est d’associer à chaque excursion le nombre de segments ascendants en dessous de l’axe des abscisses. Appelons ce nombre le défaut de l’excursion. Par exemple, l’excursion suivante a un défaut de $2$ (les segments défectueux sont en orange) :

Un chemin de Dyck aura, lui, un défaut égal à $0$. Si nous arrivons à montrer qu’il y a autant d’excursions de longueur $6$ de défaut $0$, $1$, $2$ et $3$, nous aurons prouvé qu’exactement une excursion sur $4$ est un chemin de Dyck.

Choisissons une excursion de défaut non nul, et associons-lui une nouvelle excursion en appliquant les opérations suivantes :

  • Partant de son extrémité gauche, on suit le chemin jusqu’à ce qu’il passe en dessous de l’axe des abscisses (cela peut arriver dès le premier pas).
  • On continue à suivre le chemin jusqu’à ce qu’il touche à nouveau l’axe, et on marque le dernier segment parcouru (en rouge dans la figure ci-dessous).
  • On on échange les parties du chemin avant et après le segment marqué, puis on raccorde les parties par le segment marqué.

Comme on le voit dans cet exemple, ce procédé transforme un chemin de défaut $2$ en un chemin de défaut $1$. En fait, ce procédé décroît toujours d’une unité le défaut d’un chemin. Voyez-vous pourquoi ?

Ce procédé est réversible : l’opération inverse augmente d’une unité le défaut d’un chemin. Cela implique qu’il y a bien autant d’excursions de défaut $0$, $1$, $2$, etc. La figure suivante illustre cela dans le cas des $20$ excursions de longueur $6$. Chaque colonne correspond à une valeur constante du défaut, et les flèches indiquent l’application de l’opération de permutation.

Le procédé illustré ici dans le cas de chemins à $6$ pas s’applique de manière générale. Pour tout entier positif $n$, il y a $\binom{2n}{n}$ excursions de longueur $2n$. Leur défaut est compris entre $0$ et $n$, et prend donc $n+1$ valeurs. Par conséquent, le nombre de chemins de Dyck de longueur $2n$ vaut
\[ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{2n(2n-1)\dots(n+2)}{n(n-1)\dots 1} \]
C’est donc également le nombre d’arbres binaire à $n+1$ feuilles (avec $C_0=1$ par convention, et $C_1 = \frac12 \binom{2}{1} = 1$).

Conclusion

Résumons le résultat de notre raisonnement sous la forme d’un théorème.

Théorème

L’équation du second degré $ax^2 - x + 1 = 0$ admet une solution formelle donnée par la somme infinie
\[ x = C_0 + C_1 a + C_2 a^2 + C_3 a^3 + \dots \]
où les coefficients $C_n$ sont les nombres de Catalan, donnés explicitement par
\[ C_n = \frac{2n(2n-1)\dots(n+2)}{n(n-1)\dots 1} \]

Ce résultat appelle deux commentaires :

  1. Par solution formelle, nous entendons que nous n’avons pas examiné si la somme infinie donne un résultat fini, du moins pour certaines valeurs de $a$ non nulles. Rappelons-nous que la série géométrique n’est bien définie que pour $-1< a < 1$. En fait, dans le cas présent, on peut montrer que pour tout $a$ compris entre $-\frac14$ et $\frac14$, on obtient bien un résultat fini [8]. Ce n’est pas une coïncidence que l’équation du second degré n’admet deux solutions réelles que pour $a<\frac14$.
  2. La somme infinie permet de trouver une solution, alors que l’équation du second degré peut en avoir deux. Ce n’est pas très grave, en l’occurrence, car les relations entre racines d’un polynôme (parfois appelées formules de Viète) montrent que la somme des deux solutions (ainsi que d’ailleurs leur produit) est égale à $\frac{1}{a}$. À partir d’une solution, on peut donc retrouver l’autre.

À quoi cela sert-il ?

On est bien sûr en droit de se demander quel est l’intérêt du théorème, puisque, comme nous l’avons souligné, l’équation du second degré peut être résolue exactement [9]. À quoi bon se démener avec des sommes infinies et de la combinatoire ?

Une première réponse est que si l’on ne cherche qu’une valeur approchée de la solution, la méthode décrite ici peut être plus facile à implémenter en pratique. Dans le cas $a=0,\!01$, nous avons vu que quelques termes de la somme suffisaient à donner une très bonne approximation de la solution, par un procédé qui ne fait intervenir que des additions et des multiplications. C’est bien plus simple que pour la solution exacte, qui nécessite des divisions et des racines carrées.

Un deuxième point est que la méthode que nous avons illustrée ici pour une équation du second degré peut s’appliquer à beaucoup d’autres cas. Considérons par exemple l’équation
\[ a x^n - x + 1 = 0 \]
pour $n\ge 3$. Il n’existe pas de formule générale donnant toutes les solutions d’une équation de degré $n$ si $n \ge 5$. En revanche, la méthode que nous avons discutée se généralise facilement à tous les $n$. Bien entendu, ce ne sont plus des arbres binaires qui sont impliqués (voyez-vous quels types d’arbres on doit compter ?), ni les nombres de Catalan, mais une de leurs généralisations (les nombres dits de Fuss—Catalan ou de Raney). Des méthodes similaires existent pour des équations bien plus compliquées, par exemple des équations différentielles [10]. La difficulté majeure reste souvent de déterminer quand la somme infinie donne un résultat fini. Si le problème combinatoire est trop difficile, on peut être amené à utiliser d’autres techniques pour y arriver [11].

Enfin, il est souvent très productif en mathématiques d’établir des liens entre différents domaines, comme ici entre des équations polynomiales et la combinatoire. D’ailleurs, en combinatoire énumérative, on utilise souvent une approche inverse à celle décrite ici. Supposons qu’on veuille compter le nombre $C_n$ d’un certain type d’objets mathématiques, comme des arbres, des chemins ou des mots. On appelle série génératrice l’expression formelle
\[ g(a) = C_0 + C_1 a + C_2 a^2 + C_3 a^3 + \dots \]
On essaie alors de trouver une relation de récurrence entre les $C_n$, et d’en déduire une équation satisfaite par $g$.

Par exemple, en utilisant la formule de récurrence obtenue pour le nombre d’arbres binaires, un calcul montre que
\[ g(a)^2 = C_1 + C_2 a + C_3 a^2 + \dots = \frac{g(a)-1}{a} \]
Cela implique que $g$ satisfait l’équation $ag(a)^2 - g(a) + 1=0$, qui n’est autre que l’équation dont nous sommes partis. Dans d’autres situations, on tombera sur d’autres équations pour $g$. Même si on ne sait pas les résoudre exactement, il existe des méthodes sophistiquées permettant d’en déduire beaucoup d’informations utiles, par exemple le comportement des $C_n$ pour $n$ grand.

Post-scriptum :

L’idée de base de cet article vient d’un commentaire du lecteur Christian à cet article sur les diagrammes de Feynman. J’ai eu l’occasion de mettre au point les explications lors de deux exposés devant des lycéens de seconde au Centre Galois, un stage de mathématiques en Région Centre Val de Loire. Merci aux relecteurs Himynameisarno, Daniele Turchetti, Lison, Sébastien Kernivinen et Sylvain Barré pour leurs commentaires avisés.

Article édité par Nils Berglund

Notes

[1Le premier paragraphe est partiellement adapté de cet article.

[2On aurait également pu remplacer $x$ directement par $1+a + a^2 x$.

[3On peut par exemple remarquer qu’après $n$ substitutions, on obtient
\[x = 1 + a + \dots + a^n + a^{n+1}x\]
En soustrayant $a^{n+1}x$ des deux côtés, puis en divisant par $(1-a^{n+1})$, on obtient
\[x = \frac{1 + a + \dots + a^n}{1-a^{n+1}}\]
Si $-1 < a < 1$, le résultat s’obtient en faisant tendre $a$ vers l’infini, car dans ce cas $a^{n+1}$ tend vers $0$.

[4La racine carrée de $(2a)^2$ est égale à $2|a|$, où $|a|$ est la valeur absolue de $a$. Ceci ne change toutefois rien à l’expression des deux solutions, en raison du $\pm\sqrt{\Delta}$, à part leur ordre : si $a<0$, la racine avec le signe $+$ est plus petite que celle avec le signe $-$, alors que l’ordre est inverse si $a>0$. On peut aussi remarquer que l’ensemble des solutions ne doit pas changer si on remplace $a$, $b$ et $c$ par leur opposés respectifs $-a$, $-b$, et $-c$.

[5Dans la suite, on appellera feuille toute extrémité d’un arbre, même s’il a été défeuillé.

[6Par exemple, $C_n$ compte le nombre de façons d’imbriquer correctement $n$ parenthèses ouvertes et $n$ parenthèses fermées, ou encore le nombre de triangulations d’un polygone convexe de $n+2$ côtés. C’est d’ailleurs dans ce contexte qu’en 1751, Leonhard Euler a obtenu une expression pour ces nombres.

[7La bijection entre arbres et lignes en dents de scie qui en résulte n’est pas la seule bijection possible, mais c’est la plus utile dans notre cas. Une autre bijection beaucoup utilisée consiste à faire le tour de l’arbre, partant de la racine et visitant toutes les feuilles en montant et descendant le long des branches (voir par exemple la figure 4 ici, ou la figure 6 dans cet article de Nicolas Curien). On obtient une ligne en dent de scie en représentant l’altitude en fonction du temps.

[8Cela suit du fait que
\[ \frac{C_{n+1}}{C_n} = \frac{2(2n+1)}{n+2} \]
tend vers $4$ lorsque $n$ tend vers l’infini. Par conséquent, $C_n$ se comporte, grosso modo, comme $4^n$ pour $n$ grand, et la somme infinie ressemble à la somme des $(4a)^n$, soit une série géométrique qui converge pour $-\frac14 < a <\frac14$. Le version rigoureuse de ce raisonnement s’appelle le critère de d’Alembert.

[9Une autre manière d’obtenir le résultat aurait été d’utiliser la formule du binôme généralisée de Newton pour développer $\sqrt{1-4a}$ en puissances croissantes de $a$. Pour ceux qui connaissent, on peut également utiliser un développement de Taylor—Maclaurin. Pas facile, toutefois, de généraliser cette approche à d’autres équations polynomiales...

[10Une des raisons de mon intérêt pour la combinatoire des arbres vient d’une application aux équations aux dérivées partielles stochastiques, qui est détaillée dans cet article (voir ici pour la prépublication en accès libre).

[11Par exemple, dans la théorie de Kolmogorov—Arnold—Moser, qui permet d’étudier certains types d’équations différentielles dépendant d’un petit paramètre, un outil important pour contrôler les sommes infinies est la méthode de Newton.

Partager cet article

Pour citer cet article :

Nils Berglund — «Résoudre des équations en comptant des arbres» — Images des Mathématiques, CNRS, 2018

Crédits image :

Image à la une - Les images ont été faites en LaTeX avec l’interface Tikz.

Commentaire sur l'article

  • Résoudre des équations en comptant des arbres

    le 1er novembre à 14:49, par Christian

    Bonjour Nils,

    Félicitations pour ce bel article et merci de m’en attribuer l’inspiration.
    Il y a une manne de petits théorèmes en combinatoire énumérative qui sont
    autant de chances de stimuler l’intellect de nos jeunes. Je me permets de vous suggérer la lecture de mon dernier article, en collaboration avec Nachum Dershowitz : http://crinderknecht.free.fr/pub/mm2015.pdf
    Je vous enjoint aussi de contacter Nachum de ma part, car il est le véritable expert (la bijection à la fin de l’article est sienne), et il est très intéressé par la vulgarisation (et publie des gemmes).

    Christian Rinderknecht

    Répondre à ce message
  • Résoudre des équations en comptant des arbres

    le 2 novembre à 15:05, par Nils Berglund

    Bonjour Christian,

    Merci pour le commentaire et les suggestions. J’aime beaucoup le calcul des nombres de Catalan par la bijection entre chemins de défauts différents. Je connaissais la preuve basée sur le principe de réflexion, car on l’utilise pour calculer la loi du temps de récurrence de la marche aléatoire simple sur $\mathbb{Z}$, et montrer que celle-ci est récurrente nulle. Cette approche a le mérite de se généraliser facilement au mouvement Brownien. Toutefois, la division par $n+1$ me semblait toujours un peu mystérieuse : elle suit du calcul faisant apparaître une différence de coefficients binomiaux, mais on n’a pas vraiment l’impression de comprendre pourquoi exactement $n+1$. Alors que la bijection rend ce point très clair.

    Nils Berglund

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM