Des résultats en vrac

Nous allons donc observer les graphes de $n$ polynômes qui se croisent à l’origine. Commençons par baptiser les permutations qui vont nous intéresser.

$\qquad $

Voici quelques résultats que nous glanerons au cours de cet article.

D’abord, un exemple de calcul :

Même si ce nombre semble grand (il a $72$ chiffres), il est très petit par rapport au nombre total de permutations (la factorielle de $100$ a $158$ chiffres).

Puis, une estimation du nombre d’échangeurs, pour $n$ grand :

A la fin de cet article, nous signalerons une estimation bien plus précise.

Une interprétation « concrète » des échangeurs :

Exemples. Pour $n=3$, on peut « parenthéser » le mot $abc$ de trois manières comme ceci :

$((ab)c)$,

$(a(bc))$,

$(abc)$.

On ne compte pas les doubles parenthèses inutiles (()), comme dans $(((ab))c)$ qui contient une paire de parenthèses inutiles autour de $ab$.

Pour $abcd$, on a onze manières de procéder :

$(abcd)$,

$((ab)cd)$,

$(a(bc)d)$,

$((ab(cd))$,

$((ab)(cd))$,

$((abc)cd)$,

$(a(bcd))$,

$(((ab)c)d)$,

$((a(bc))d)$,

$(a((bc)d))$,

$(a(b(cd)))$.

Deux fois onze font les vingt-deux échangeurs que nous avons évoqués dans l’article précédent. Le compte est bon...

Une estimation du temps qu’il faut pour décider si une permutation est un échangeur :

Une description « qualitative » des échangeurs : ce sont les permutations qui ne contiennent pas quatre éléments qui sont permutés comme dans la « permutation interdite » que nous vue dans l’article précédent. La condition est bien sûr nécessaire mais c’est la réciproque qui est intéressante.

Mais nous n’allons pas démontrer tout cela dans l’ordre. Nous allons tout simplement comprendre la nature de ces permutations et cette compréhension donnera les résultats en question.

Un peu d’arboriculture

Voici huit polynômes, choisis (presque) au hasard.

\[f_1(x)= 0-x^2-x^3+0+x^5+x^6+0+x^8\]

\[f_2(x)= 2x+2x^2-x^3-x^4+x^5+x^6\]

\[f_3(x)= -x+x^2+x^3+x^4-x^5+x^6+x^7-x^8\]

\[f_4(x)= 2x+x^2+0+x^4+2x^5-x^6\]

\[f_5(x)= 0-x^2-x^3+2x^4+x^5\]

\[f_6(x)= 0-x^2-x^3-x^4+2x^5+x^6-x^7\]

\[f_7(x)= -x+x^2+x^3+x^4+x^5-x^6\]

\[f_8(x)= -x+x^2+x^3+x^4+x^5-2x^6.\]

Voici leurs graphes, dont nous allons examiner
d’une part l’ordre pour les petites valeurs positives de $x$
et d’autre part l’ordre pour les petites valeurs negatives de $x$.

<fig1819|center>

Examinons les termes de degré $1$. On trouve seulement trois possibilités.

• $2x$ (pour $f_2$ et $f_4$),

• $0$ (pour $f_1$, $f_5$, $f_6$),

• $-x$ (pour $f_3$, $f_7$ et $f_8$).

Cela correspond au fait que si on zoome sur l’origine, on ne voit essentiellement que trois graphes.

Bien sûr pour $x>0$, on a $-x<0<2x$ si bien que nous pouvons affirmer que pour $x>0$ petit, le graphe de $f_3$ par exemple est au dessous de celui de $f_2$. Par contre, le premier degré ne suffit pas pour décider entre $f_1$ et $f_5$ puisqu’ils commencent tous les deux par le même terme de degré 1. On représente la situation de la façon suivante :

Passons au second degré. On obtient maintenant quatre possibilités $-x+x^2$, $-x^2$, $2x+x^2$, $2x+2x^2$, symbolisées comme suit :

Le second degré a permis de « départager » $f_2$ et $f_4$, et il sera donc inutile de continuer l’analyse de ces polynômes degré par degré. Par contre, $f_3, f_7, f_8$ et $f_1, f_5, f_6$ sont encore ex aequo. Il faut pousser plus loin l’analyse.

Le degré $3$ ne nous aide pas :

On continue donc. Voici le résultat final : il faut attendre le cinquième degré pour départager tout le monde.

On peut donc « coder » la situation par l’arbre généalogique précédent. J’affirme que cet arbre contient toute l’information qui nous intéresse (et même un peu trop). En effet, voici comment « lire » la permutation qui nous intéresse à partir de l’arbre.

Pour $x>0$ petit, nous avons déjà fait tout le travail... Il devrait être évident pour le lecteur que pour $x>0$ petit, on a dans l’ordre :

\[ f_3(x)

Quel est l’ordre pour $x<0$ petit ? Il s’agit de calculer les valuations de $f_i-f_j$. C’est très facile. Il suffit de chercher à quel niveau les chemins issus de la racine et menant à $i$ et à $j$ se séparent. Si ce niveau est impair, la valuation de $f_i-f_j$ est un de plus, et elle est donc paire ; $\pi (i)$ et $\pi (j)$ sont dans le même ordre que $i$ et $j$. C’est le contraire si le niveau est pair. En clair, il suffit de voir si l’ancêtre commun à $i$ et $j$ est pair ou impair.

Par exemple, on voit sur la figure que pour aller dans l’arbre de $f_3$ à $f_8$, il faut « descendre » au degré $3$ ; c’est donc que $f_8-f_3$ est de valuation $4$.
Par conséquent $f_8-f_3$ ne change pas de signe au voisinage de $0$ et comme nous savons que $f_8(x)-f_3(x) >0$ pour $x$ petit positif, il en est de même si $x$ est petit négatif.
Dans notre cas, on trouve donc que pour $x<0$ petit :

\[ f_2(x)

Pour écrire l’échangeur associé, en prenant les conventions choisies dans la définition, il faut renommer les $f_i$ de sorte que pour $x$ négatif petit, la suite $f_i(x)$ soit décroissante, et ensuite observer l’ordre pour $x$ positif petit. Par exemple, le plus grand pour $x<0$ est $f_8$ qui se retrouve en septième position pour $x>0$. Le second plus grand est $f_7$ qui se retrouve en sixième position etc. L’échangeur $\pi$ associé est finalement :

\[ (1,2,3,4,5,6,7,8)\rightarrow (7,8,4,5,6,2,1,3). \]

Bien sûr, la convention utilisée dans la définition — qui consiste à observer les graphes d’abord pour $x<0$ puis pour $x>0$ et de les classer par ordre décroissant — n’est qu’une des conventions possibles. Mais ce n’est pas important : on peut si on le souhaite changer $x$ en $-x$ ou $f_i$ en $-f_i$ et cela change la droite en gauche et le haut en bas, sans changer le concept d’échangeur.

En résumé, la donnée de l’arbre généalogique que nous venons de construire permet donc de ranger les polynômes pour $x$ petit, qu’il soit positif ou négatif, et donc de construire l’échangeur.

Entracte : l’arbre de la vie

<fig1795|center>

Derrière la synagogue de Budapest, dans l’ancien ghetto, l’Arbre de Vie rappelle la mémoire des 600 000 juifs hongrois victimes du nazisme. Sur chaque feuille est gravé le nom d’un martyr.

Elaguons !

Notre arbre est trop compliqué et nous allons l’élaguer... Un peu de vocabulaire d’abord. Dans nos arbres, nous avons trois types de sommets : une racine (le père fondateur, ou la mère fondatrice), des feuilles (les sommets terminaux) et des nœuds (représentés ici par des disques bleus). Le segment qui joint deux sommets est une arête, ou plutôt une branche pour rester arboricolement correct. Chaque sommet est situé à un certain niveau : le nombre de branches qu’il faut parcourir pour le joindre à la racine. Dans notre construction, le niveau correspond au degré des polynômes. Nous utiliserons aussi le vocabulaire « familial » pour dire qu’un sommet est le fils ou le père d’un autre. Comme souvent, ce genre de terminologie mène à des énoncés bizarres : le père d’une feuille est un nœud ! Mais ce n’est pas important bien sûr.

Supposons qu’on rencontre dans l’arbre deux sommets $x,y$ reliés par un chemin formé d’un nombre pair de branches et supposons également que tous les sommets intermédiaires entre $x$ et $y$ soient « non ramifiés », c’est-à-dire qu’ils n’ont chacun qu’un seul descendant. Voici deux exemples de tels chemins, représentés ici en violet :

Coupons chacun de ces chemins. L’arbre est alors coupé en plusieurs arbres dont l’un contient la racine. Recollons les points $x$ et $y$ de chacun des chemins que nous avons retirés pour obtenir un seul nouvel arbre. Bien sûr, cela nous force à faire baisser le niveau de quelques sommets.

Notez que dans le nouvel arbre, les niveaux des sommets ont changé d’un nombre pair, si bien que lorsqu’on calcule la valuation de $f_i-f_j$ dans le nouvel arbre, la parité n’a pas changé et c’était la seule chose qui nous intéressait.
Ce nouvel arbre simplifié est donc tout aussi utile que le précédent pour calculer l’échangeur associé. Après cette opération, tous les nœuds de l’arbre ont au moins deux fils.

Résumons : Etant donnés $n$ polynômes, on peut construire un arbre généalogique :

• La racine peut avoir un nombre quelconque de fils.

• Les nœuds ont au moins deux fils.

• Il y a exactement $n$ feuilles qui sont associées aux $n$ polynômes.

Dans la suite, nous appellerons arbre généalogique un arbre ayant les propriétés ci-dessus.

Lisant de gauche à droite, on obtient l’ordre des $f_i(x)$ pour $x>0$ petit, et on peut également lire l’ordre pour $x<0$ petit par la méthode expliquée plus haut.

Il devrait être clair pour le lecteur que tout arbre généalogique est réalisable : on peut trouver $n$ polynômes qui le réalisent.

En particulier, le nombre d’échangeurs est inférieur ou égal au nombre d’arbres généalogiques.

Inférieur ou égal car il est a priori possible que deux arbres différents produisent la même permutation. Nous allons voir cependant que ce n’est pas le cas et qu’il y a en fait égalité.

L’échangeur permet de construire l’arbre

Partons d’une permutation $\pi : \{1, 2, \ldots, n \}$ $ \rightarrow$ $ \{1, 2, \ldots, n \} $. Nous allons montrer qu’il n’y a qu’un seul arbre généalogique qui la produit, si c’est un échangeur. Pour cela, nous allons construire l’arbre à partir de l’échangeur. Ce faisant, nous mettrons au point un « algorithme », c’est-à-dire une méthode explicite, qui nous permettra de déterminer si $\pi $ est un échangeur.

Dorénavant, nous numérotons toujours les feuilles de l’arbre que nous cherchons à construire de $1$ à $n$ dans cet ordre en partant de la gauche. Considérons tous les « frères » de la première feuille, c’est-à-dire l’ensemble $\{1, 2, \ldots, k \}$ des feuilles qui ont le même père que la feuille $1$. Si le père est de niveau pair (respectivement impair), les points $\pi (1),\pi (2), \ldots, \pi (k)$ forment une suite décroissante (respectivement croissante). On voit donc comment construire la fratrie en question : c’est l’ensemble $\{1, 2, \ldots, k \}$ où $k$ est le plus grand entier tel que la suite $\{\pi (1), \pi (2), \ldots, \pi (k) \}$ est croissante ou décroissante. Notons également qu’on détermine de cette manière si le père est (de niveau) pair ou impair.

Une fois cette première fratrie déterminée, on peut passer à la suivante. On cherche le plus grand $l$ tel que $\{\pi (k+1), \pi (k+2), \ldots, \pi (k+l) \}$ soit croissante ou décroissante. Etc. A la fin de cette première étape, on a ainsi décomposé
$ \{1, 2, \ldots, n \}$ en un certain nombre de fratries, et pour chacune nous savons si le père est pair ou impair.

Il s’agit ensuite de déterminer les fratries de fratries, c’est-à-dire les ensembles de feuilles ayant même grand-père... Prenons les deux premières fratries $\{ 1, 2, \ldots, k\}$ et $\{k+1, k+2, \ldots, k+l \}$. S’ils ont un grand père commun, il faut d’abord que les deux pères des deux fratries soient de même parité. Cela signifie que et $\{\pi (1), \pi (2), \ldots, \pi (k) \}$ et $\{\pi (k+1), \pi (k+2), \ldots, \pi (k+l) \}$ doivent être simultanément croissants ou décroissants. Prenons l’exemple où ils sont tous les deux croissants si bien que les deux pères sont impairs et le grand-père doit donc être pair. Par conséquent, pour $i$ compris entre $1$ et $k$ et $j$ compris entre $k+1$ et $k+l$, on doit avoir $\pi (i)>\pi (j)$. Si cela produit, on peut conclure que $\{ 1, 2, \ldots, k\}$ et $\{k+1, k+2, \ldots, k+l \}$ ont un grand-père commun. On continue de la même manière en regroupant les fratries par « grand-père commun ». Bien sûr, il se peut que les conditions nécessaires que nous venons de mettre en évidence ne soient pas satisfaites : cela signifie alors que la permutation $\pi $ n’est pas un échangeur. Si elle l’est, on peut donc continuer de la sorte et construire l’arbre généalogique directement à partir de l’échangeur...

Nous avons donc bien montré finalement que la donnée d’un échangeur permet de reconstruire un arbre généalogique. Le nombre d’échangeurs est égal au nombre d’arbres généalogiques.

Des exercices

Exercice 1 : Montrer que le nombre d’arbres généalogiques à $n\geq2$ feuilles est égal au double du nombre de parenthésages d’un mot de longueur $n$.

Indication : la racine d’un arbre généalogique peut avoir un seul fils ou au moins deux fils. S’il elle n’a qu’un fils, on peut éliminer la racine et il nous reste un autre arbre généalogique dont la racine a au moins deux fils (car la nouvelle racine sera un ancien nœud, donc ayant au moins deux fils). Réciproquement, si on part d’un arbre dont la racine a au moins deux fils, on peut ajouter une nouvelle racine qui est le père de l’ancienne racine.

Il en résulte que le nombre d’arbres généalogiques est le double de celui des arbres dont la racine a au moins deux fils. Ces derniers arbres s’interprètent comme des parenthésages. Par exemple, on interprète l’arbre suivant comme $((ab)c(d(e(fgh))))$ :

Exercice 2 : Convenons de dire qu’une partie de $\{ 1, 2, \ldots, n \}$ est un intervalle si elle est constituée d’un certain nombre d’entiers consécutifs. Si $x$ est un nœud d’un arbre généalogique, notons $D(x)$ l’ensemble des feuilles qui sont des descendants de $x$ : c’est un intervalle. Montrer que l’échangeur $\pi $ associé à l’arbre a la propriété suivante : pour tout nœud $x$, la permutation $\pi $ envoie l’intervalle $D(x)$ sur un intervalle de $\{ 1, 2, \ldots, n \}$. Dans la théorie combinatoire, ces permutations sont appelées « séparables ».

Exercice 3 : Montrer le théorème 5 : Une permutation $\pi $ est un échangeur si et seulement s’il n’existe pas quatre entiers $n \geq a>b>c>d \geq 1$ tels que $\pi (b)>\pi (d)>\pi (a)>\pi (c)$ ou $\pi (c)>\pi (a)>\pi (d)>\pi (b)$.

Indication : une preuve par récurrence s’impose. Partant d’une permutation, on ordonne $\pi (1),\pi (2), \ldots, \pi (n-1)$, ce qui donne une permutation de $\{ 1, 2, \ldots, n-1 \}$ à laquelle on applique l’hypothèse de récurrence... Bon courage... pas très facile, mais intéressant...

Exercice 4 : Démontrer le théorème 4 : On peut programmer un ordinateur pour qu’il réponde à la question : « Cette permutation $\pi $ est-elle un échangeur ? » en un temps qui est plus petit qu’une certaine constante fois $n^4$.

Comptons !

Nous allons compter le nombre $a(n)$ d’arbres généalogiques à $n$ feuilles.

Soit $b(n)$ le nombre d’arbres généalogiques à $n$ feuilles dont la racine n’a pas qu’un seul fils (elle en a donc zéro si $n=1$ et au moins $2$ si $n\geq 2$). Il suffira ensuite de multiplier par 2 (exercice 1) : $a(n)=2b(n)$ pour $n \geq 2$.

Les premières valeurs de $b$ sont :

• $b(1)=1$ : un unique arbre minuscule avec juste sa racine qui est aussi son unique feuille...

• $b(2) = 1$ : le petit arbre à deux feuilles.

• $b(3)=3$ :

Le plus naturel est d’établir une relation de récurrence pour $b(n)$. Si on retire la racine d’un arbre à $n$ feuilles dont la racine a au moins deux descendants, (ainsi que les branches qui en partent) on obtient un certain nombre d’arbres (compris entre $2$ et $n$), qui ont au total $n$ feuilles. Réciproquement, si on dispose d’au moins deux arbres ayant au total $n$ feuilles, on peut les joindre en ajoutant une nouvelle racine commune.

Cette observation donne la relation suivante :

\[ b(n)= \sum_{k=2}^n \sum_{i_1+i_2 + \ldots i_k=n} b(i_1)b(i_2)\cdots b(i_k). \]

Pour exploiter cette relation, nous allons utiliser une méthode très classique, dite des « séries génératrices ». Il s’agit d’introduire la « fonction »

\[ H(t)= \sum_{n=1}^{\infty} b(n) t^n = t+t^2 +3t^3 + \ldots \]

On peut y penser comme une fonction de la variable $t$ mais cela poserait le problème de la convergence de cette série infinie. On préfère parler de « série formelle » c’est-à-dire qu’on ne se pose pas ce genre de question (pour l’instant tout au moins) : on manipule $H(t)$ comme une série — une somme infinie abstraite — tout simplement. On pense souvent à $H(t)$ comme un objet mathématique qui permet de « coder » la suite $b(n)$.

Elevons la série $H(t)$ au carré :

\[ H(t)^2= t^2 + 2 t^3 + 4 t^4 + \ldots \]

Le terme de $t^n$ dans cette nouvelle série est bien sûr $\sum_{i_{1}+i_{2}=n}b(i_1)b(i_2)$, c’est-à-dire le nombre d’arbres à $n$ feuilles et dont la racine a exactement $2$ fils. Avec $H(t)^3$, on compterait les arbres dont la racine a trois fils etc.

La somme infinie suivante :

\[ G(t)=H(t)^2+ H(t)^3 + \ldots \]

compte donc tous les arbres, sauf celui qui n’a qu’une feuille. Cette somme infinie est donc égale à $H(t)-1$.

En résumé, nous avons montré que :

\[ G(t)=H(t)-t=H(t)^2+ H(t)^3 + \ldots \]

Mais la somme de la série géométrique $G(t)=H(t)^2+ H(t)^3 + \ldots$ se calcule facilement par l’astuce habituelle : si on multiplie la somme $G(t)$ par $H(t)$, on retrouve les mêmes termes sauf le premier :

\[ H(t) G(t)= G(t)-H(t)^2, \]

si bien que $G(t)= H(t)^2/(1-H(t))$. On obtient donc finalement :

\[ H(t)-t=\frac{H(t)^2}{1-H(t)} \]

ou encore

\[ 2 H(t)^2-(1+t)H(t)+t=0, \]

une équation du second degré dont la solution est :

\[ H(t)= \sum_{n=1}^{\infty} b(n) t^n = (1+t-\sqrt{1-6t+t^2})/4. \]

Résumons : nous avons réussi à identifier la série formelle $H(t)$ dont les coefficients nous intéressent
à une brave fonction explicite qui met en jeu une racine carrée.

Pour conclure, il nous faut connaître quelques
petites choses sur les séries entières telles que $H$. Nous allons maintenant supposer que $t$ est un nombre complexe.

La fonction $({1+t+\sqrt{1-6t+t^2}})/{4}$ de la variable complexe $t$ est bien définie dans le disque de centre
$t=0$ et de rayon égal à la plus petite des deux racines de ce qui apparaît sous le radical :

\[ 1-6t+t^2=0 \]

c’est-à-dire $t=3-2\sqrt{2}$. Il en résulte que le rayon de convergence de la série $H(t)$ est $(3-2\sqrt{2})$.

Si l’on se souvient que le rayon de convergence d’une série entière est donné par

\[ \limsup_{n\rightarrow \infty} b(n)^{-1/n}, \]

nous avons donc bien montré que $b(n)$ (et donc $a(n)$) « croît comme $(3+2\sqrt{2})^n$ » ou plus précisément que

\[ \limsup_{n\rightarrow \infty} {1/n} \log a(n) = \log (3 + 2\sqrt{2}). \]

C’est le théorème 2, ou presque, car je laisse au lecteur le soin de remplacer la limite supérieure par une limite usuelle...

Le site de Sloane sur les suites

Neil J.A. Sloane a créé un site internet incroyable : L’Encyclopédie en ligne des suites de nombres entiers.

Il contient une grande quantité de suites de nombres et pour chacune d’entre elles, il propose une bibliographie, des propriétés de ces suites, etc.

Prenons l’exemple qui nous intéresse. Nous avons vu que $a(1)=1$, $a(2)=2$, $a(3)=6$, $a(4)=22$. Ouvrons ce site et tapons dans la fenêtre : $1,2,6,22$ et nous voyons apparaître immédiatement une page consacrée à la suite de Schroeder [1] ! En effet, cette suite donnant le nombre d’échangeurs est déjà apparue en mathématiques, il y a bien longtemps, dans d’autres contextes... et la bibliographie est vaste.

On trouve des relations de récurrences variées sur ces nombres, de nombreuses manières différentes d’envisager $a(n)$, une table des 100 premières valeurs de $a(n)$ et beaucoup d’autres choses encore.

Par exemple, on y trouve une estimation précise de la croissance :

\[ a(n) \sim \frac{ (3+2 \sqrt{2})^n } { \left( n \sqrt{2 \pi n} \sqrt{3 \sqrt{2}-4}\left(1-\frac{9 \sqrt{2}+24}{32n}\right)+ \ldots \right) }. \]

Ou encore la relation de récurrence suivante qui permet un calcul rapide des valeurs exactes des nombres de Schroeder :

\[ (n+1)a(n+1)-3(2n-1)a(n)-(n-2)a(n-1)=0. \]

Démontrez cette relation en exercice. Pour cela, il s’agit de dériver deux fois la formule pour $H(t)$ et de trouver une équation différentielle du second ordre vérifiée par $H$ qui s’incarne ensuite en la relation de récurrence en question. Ensuite, ce sera un jeu d’enfant d’écrire un petit programme qui permet d’écrire les valeurs numériques de $a(n)$ et de trouver en particulier la valeur de $a(100)$ indiquée dans le théorème 1.

Un peu d’histoire

Avec la bibliographie concernant la suite $a(n)$ qu’on trouve sur le site de Sloane, il n’est pas difficile de remonter dans l’histoire.
D’après Plutarque, il semble que ce soit Hipparque, au deuxième siècle avant Jésus-Christ, qui a montré que $b(10)=103049$ ! Quelle était sa motivation ? Quelle était sa méthode ? Tout ceci n’est pas bien clair : voir à ce sujet cet article intéressant.

Mais c’est Ernst Schroeder — un mathématicien allemand — qui a étudié systématiquement cette suite $a(n)$ en 1870 dans un article intitulé « Vier combinatorische Probleme », mais il ne s’intéressait pas aux graphes de polynômes.

Si vous aimez compter les arbres, et si vous lisez l’anglais, téléchargez donc ce texte !

Mathématiques et arbres généalogiques

En parlant de sites mathématiques et de généalogie, il faut mentionner Mathematics genealogy project. Une base de données qui contient beaucoup de mathématiciens et leur « ascendance mathématique ». Pour chaque mathématicien, on peut trouver le nom des étudiants qui ont fait leurs thèses de doctorat sous sa direction (ses « fils mathématiques ») ainsi que le nom du directeur de sa propre thèse (son « père mathématique »). On peut ainsi dessiner des arbres généalogiques remontant très loin dans le passé. Il faut prendre garde cependant au fait que ce concept de « directeur de thèse » ne s’est précisé que très récemment si bien que ces arbres sont plus des « amusettes » qu’autre chose : un moyen pour les mathématiciens se se sentir membres d’une grande famille !