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 là 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.

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$.

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 :

À 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 !

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$.

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.

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.