Arbre de Stern-Brocot

En mathématiques, l'arbre de Stern-Brocot est une représentation de tous les rationnels strictement positifs, sous forme d'arbre binaire. Chaque nombre rationnel est représenté sous forme de fraction irréductible. Ils sont présents une et une seule fois, et sont tous représentés par cet arbre.

Il a été découvert presque simultanément par le mathématicien allemand Moritz Stern (1858) et par l'horloger français Achille Brocot (1861).

Ses propriétés permettent de réaliser une bijection entre tous les rationnels et tous les entiers, en codant tout nœud de l'arbre, et donc tous les rationnels, par un nombre binaire et d'établir des lien directs entre cette représentation et les fractions continues.

Modèle:Clr

Construction

L'arbre de Stern-Brocot est un arbre binaire infini dont les nœuds sont étiquetés par les fractions irréductibles. On le construit par récurrence, un étage après l'autre.

L'étage 1 contient uniquement la racine de l'arbre, portant la fraction 1/1.

L'étage p+1 de l'arbre est construit ainsi : on liste toutes les fractions du sous-arbre fini correspondant à l'étage p, lues de gauche à droite. On insère la fraction 0/1 en tête de liste et 1/0 en queue de liste, obtenant ainsi une liste de 2Modèle:Exp+1 fractions (voir image). Dans cette liste, une fraction sur deux appartient à l'étage p, une sur quatre à l'étage p − 1, etc.

À chaque fraction appartenant à l'étage p, on associe ses deux filles de niveau p + 1 obtenues en faisant la médiane avec chacune de ses deux voisines dans la liste : la médiane des fractions $\frac{m}{n}$ et $\frac{m^{'}}{n^{'}}$ est la fraction $\frac{m + m^{'}}{n + n^{'}}$ .

Exemple : les premiers étages de l'arbre

Voici les listes de fractions contenues dans l'arbre après construction de chacun des 4 premiers étages (également représentés sur le dessin) auxquelles on a ajouté 0/1 en premier, 1/0 en dernier. À chaque étage, on a colorié en rouge les fractions ajoutées à cet étage, les autres étant celles des étages précédents ; ainsi les fractions rouges sont les nœuds de l'arbre de Stern-Brocot. Ils se calculent comme la médiane (voir définition ci-dessus) des nombres en noir adjacents.

$\begin{matrix} Étage 1 : & \frac{0}{1} & \frac{1}{1} & \frac{1}{0} \\ Étage 2 : & \frac{0}{1} & \frac{1}{2} & \frac{1}{1} & \frac{2}{1} & \frac{1}{0} \\ Étage 3 : & \frac{0}{1} & \frac{1}{3} & \frac{1}{2} & \frac{2}{3} & \frac{1}{1} & \frac{3}{2} & \frac{2}{1} & \frac{3}{1} & \frac{1}{0} \\ Étage 4 : & \frac{0}{1} & \frac{1}{4} & \frac{1}{3} & \frac{2}{5} & \frac{1}{2} & \frac{3}{5} & \frac{2}{3} & \frac{3}{4} & \frac{1}{1} & \frac{4}{3} & \frac{3}{2} & \frac{5}{3} & \frac{2}{1} & \frac{5}{2} & \frac{3}{1} & \frac{4}{1} & \frac{1}{0} \end{matrix}$

Propriétés élémentaires : lien avec les suites de Farey

L'arbre de Stern-Brocot est étroitement lié aux suites de Farey. Rappelons que deux fractions irréductibles m/n et mModèle:'/nModèle:' sont voisines de Farey si on a :

m^{'} n - m n^{'} = 1

Dans ce cas, on vérifie (voir plus bas) que leur médiane est voisine de Farey, à droite de la première, à gauche de la seconde. Ceci a en particulier comme conséquence que Modèle:Nobr ; on en déduit qu'à chaque étage p de l'arbre de Stern-Brocot, la liste associée des Modèle:Nobr fractions apparaissant dans le sous-arbre est ordonnée de la plus petite à la plus grande et que deux fractions consécutives dans cette liste sont voisines de Farey. Cette dernière propriété entraîne de plus que toutes les fractions apparaissant dans l'arbre sont irréductibles.

Notons que la branche de gauche de l'arbre contient toutes les fractions unitaires, tandis que la branche de droite contient tous les nombres entiers écrits sous forme de fractions de dénominateur égal à 1.

À chaque étage, les dénominateurs des fractions figurant sur la liste associée forment la suite diatomique de Stern.

Arbre de Stern-Brocot et algorithme d'Euclide

L'arbre de Stern-Brocot, comme les suites de Farey, est également lié à l'algorithme d'Euclide ; celui-ci permet en effet, étant donné une fraction m/n, de calculer le chemin menant de la racine à celle-ci.

On utilise pour cela le théorème de Bachet-Bézout : si l'on suppose que m/n est irréductible, c'est-à-dire que m et n sont premiers entre eux, alors il existe deux entiers m' et n' tels que Modèle:Nobr (ou Modèle:Nobr) ; si de plus on suppose que m et n sont distincts et tous les deux non nuls, alors on peut choisir m' et n' de façon que Modèle:Nobr et Modèle:Nobr (les coefficients mModèle:' et nModèle:' satisfaisant toutes ces contraintes sont directement calculés par l'algorithme d'Euclide étendu). Dans ce cas comme on a vu plus haut, les fractions mModèle:'/nModèle:' et m/n sont voisines de Farey.

On pose alors Modèle:Nobr et Modèle:Nobr ; si Modèle:Nobr alors Modèle:Nobr, sinon Modèle:Nobr et donc Modèle:Nobr. De plus m/n est la fraction médiane de mModèle:'/n' et Modèle:Nobr d'où l'on déduit Modèle:Nobr si Modèle:Nobr, ou Modèle:Nobr si Modèle:Nobr. Dans l'arbre de Stern-Brocot, la fraction Modèle:Nobr est la fille de celle des deux fractions Modèle:Nobr et Modèle:Nobr qui a le plus grand dénominateur puisque c'est celle-ci qui se trouve à l'étage le plus bas, et l'on détermine s'il s'agit de la fille gauche ou droite en fonction du signe de Modèle:Nobr.

Par exemple si l'on considère la fraction 2/5 alors l'algorithme d'Euclide nous donne Modèle:Nobr. On en déduit que 1/2 et Modèle:Nobr sont les voisines de 2/5 dans la suite de Farey d'ordre 5 ; comme 1/3 a le plus grand dénominateur elle est la mère de 2/5 ; de plus l'équation Modèle:Nobr implique que Modèle:Nobr, donc que Modèle:Nobr, d'où l'on déduit que 2/5 est la fille droite de 1/3.

En itérant l'argument ci-dessus, on peut montrer par récurrence que l'on produit une suite finie de fractions de fille en mère, c'est-à-dire un chemin dans l'arbre remontant de la fraction initiale vers la racine. En particulier ceci donne une démonstration de l'existence de chaque fraction irréductible dans l'arbre.

Énumération des rationnels

La propriété fondamentale de l'arbre de Stern-Brocot est qu'il contient toutes les fractions irréductibles strictement positives une et une seule fois chacune. On en déduit un procédé pour numéroter tous les rationnels positifs, c'est-à-dire une bijection des rationnels positifs sur les entiers naturels positifs. En bref on associe à un rationnel l'entier dont la représentation en base 2 code le chemin de la racine de l'arbre au rationnel choisi.

Étant donné une fraction on lui associe une suite de 0 et de 1 représentant le chemin issu de la racine de l'arbre et menant à celle-ci. On définit donc deux « pas » : le pas 0 (gauche) et le pas 1 (droite) (dans le livre cité en référence, ceux-ci sont notés L pour left et R pour right). Par exemple le chemin menant à la fraction 2/5 est représenté par la suite (0, 0, 1) : depuis la racine descendre 2 fois à gauche puis 1 fois à droite. Pour simplifier on notera désormais les suites de 0 et de 1 comme des mots binaires, par exemple la suite (0, 0, 1) sera représentée par le mot binaire 001.

L'idée est maintenant de lire le mot binaire associé à une fraction comme la représentation en base 2 d'un entier. Toutefois comme plusieurs mots binaires peuvent représenter le même entier (par exemple les mots 1, 01, 001, ..., représentent tous l'entier 1) on va d'abord préfixer la représentation du chemin par un 1. Si on reprend l'exemple du rationnel 2/5, son chemin est représenté par le mot 001, qui lorsqu'il est préfixé par 1 devient 1001 ce qui se lit comme la représentation en base 2 de l'entier 9. De même le rationnel 3/5 est associé à l'entier $(1010)_{2} = 10$ , le rationnel 5/2 à $(1110)_{2} = 14$ , etc. Ainsi on affecte un unique numéro à tout rationnel et réciproquement tout entier, écrit en base 2, peut s'interpréter comme un chemin dans l'arbre menant à un rationnel.

Modèle:Démonstration/début

Irréductibilité de chaque fraction

On montre que chaque fraction apparaissant dans l'arbre est irréductible par récurrence.

On rappelle que la liste associée au p-ième étage de l'arbre de Stern-Brocot est la liste des $2^{p + 1} - 1$ fractions contenues dans le sous-arbre de hauteur p, lues de gauche à droite, à laquelle on ajoute 0/1 en tête et 1/0 en queue. On va montrer formellement la propriété énoncée plus haut : deux fractions consécutives dans la liste sont voisines de Farey.

Initialisation : À l'étage 0, c'est évident : on a Modèle:Nobr.

Hérédité : Supposons par récurrence la propriété vérifiée à l'étage p.

Par construction les nouvelles fractions apparaissant à l'étage Modèle:Nobr sont des médianes (m + mModèle:')/(n + nModèle:') où m/n et mModèle:'/nModèle:' sont consécutives dans la liste associée à l'étage p ; par hypothèse de récurrence on a Modèle:Nobr. Il faut voir que les fractions m/n, Modèle:Nobr et mModèle:'/nModèle:' qui sont consécutives dans la liste associée à l'étage Modèle:Nobr sont voisines de Farey ce qui se déduit des calculs suivants :

(m + m^{'}) n - m (n + n^{'}) = m^{'} n - m n^{'} = 1, m^{'} (n + n^{'}) - (m + m^{'}) n^{'} = m^{'} n - m n^{'} = 1 .

Ainsi toutes les paires m/n et mModèle:'/nModèle:' de fractions consécutives de la liste associée à l'étage Modèle:Nobr vérifient m'n - mn' = 1 ce qui est une relation de Bézout d'où l'on déduit en particulier que m et n sont premiers entre eux, donc que m/n (ainsi que m'/nModèle:') est irréductible.

Unicité

On veut montrer que chaque fraction strictement positive apparaît au plus une fois dans l'arbre. C'est une conséquence du fait qu'à chaque étage la liste associée est strictement croissante, qui lui-même est conséquence du fait démontré ci-dessus que les fractions consécutives dans la liste associée à l'étage p sont voisines de Farey ; en effet Modèle:Nobr entraîne en particulier que Modèle:Nobr donc que Modèle:Nobr.

Existence

On a déjà vu en utilisant l'algorithme d'Euclide que toute fraction irréductible apparaît dans l'arbre. On donne en donne ici une autre démonstration.

Considérons une fraction irréductible notée a/b. On va construire quatre suites d'entiers $(m_{p})$ , $(n_{p})$ , $(m'_{p})$ et $(n'_{p})$ par récurrence sur p :

Pour p = 0 on pose $m_{0} = 0$ , $n_{0} = 1$ , $m'_{0} = 1$ et $n'_{0} = 0$ .

À l'étape p trois cas s'offrent à nous :

$\frac{m_{p} + m'_{p}}{n_{p} + n'_{p}} = \frac{a}{b}$ : on pose alors $m_{p + 1} = m'_{p + 1} = a$ et $n_{p + 1} = n'_{p + 1} = b$ .
$\frac{m_{p} + m'_{p}}{n_{p} + n'_{p}} < \frac{a}{b}$ : on pose $m_{p + 1} = m_{p} + m'_{p}$ ; $n_{p + 1} = n_{p} + n'_{p}$ ; $m'_{p + 1} = m'_{p}$ et $n'_{p + 1} = n'_{p}$ .
$\frac{m + m^{'}}{n + n^{'}} > \frac{a}{b}$ : on pose $m_{p + 1} = m_{p}$ ; $n_{p + 1} = n_{p}$ ; $m'_{p + 1} = m_{p} + m'_{p}$ et $n'_{p + 1} = n_{p} + n'_{p}$ .

Cette définition a plusieurs conséquences facilement vérifiables par récurrence :

les quatre suite d'entiers $(m_{p})$ , $(n_{p})$ , $(m'_{p})$ et $(n'_{p})$ sont croissantes (mais pas strictement croissantes).

pour tout p si les fractions $m_{p} / n_{p}$ et $m'_{p} / n'_{p}$ sont différentes alors on a $m_{p} / n_{p} < a / b < m'_{p} / n'_{p}$ , elles sont consécutives dans la liste associée à l'étage p, donc en particulier voisines de Farey, ce qui entraîne notamment qu'elles sont irréductibles. De plus l'une des deux appartient à l'étage p et donc leur médiane appartient à l'étage Modèle:Nobr. En effet dans la liste associée à l'étage p une fraction sur deux appartient à l'étage p, par conséquent la médiane de deux fractions consécutives appartient à l'étage Modèle:Nobr.

pour tout p si les fractions $m_{p} / n_{p}$ et $m'_{p} / n'_{p}$ sont égales alors elles sont toutes deux égales à a/b et il en est de même de $m_{q} / n_{q}$ et $m'_{q} / n'_{q}$ pour tout $q \geq p$ .

On veut montrer qu'il existe un p tel que $a / b = m_{p + 1} / n_{p + 1} = m'_{p + 1} / n'_{p + 1}$ ; si un tel p existe alors en supposant que c'est le plus petit, on a $a / b = (m_{p} + m'_{p}) / (n_{p} + n'_{p})$ et comme la médiane appartient alors à l'étage Modèle:Nobr cela démontre que l'on a trouvé $a / b$ dans l'arbre.

Comme $a / b > m_{p} / n_{p}$ on a $a n_{p} - b m_{p} > 0$ et comme $a n_{p} - b m_{p}$ est entier on en déduit $a n_{p} - b m_{p} \geq 1$ . De même de $a / b < m'_{p} / n'_{p}$ on déduit $b m'_{p} - a n'_{p} \geq 1$ . En multipliant ces deux inéquations respectivement par $m'_{p} + n'_{p}$ et $m_{p} + n_{p}$ on obtient : $(m'_{p} + n'_{p}) (a n_{p} - b m_{p}) + (m_{p} + n_{p}) (b m'_{p} - a n'_{p}) \geq m'_{p} + n'_{p} + m_{p} + n_{p}$ .

Or, en utilisant le fait que $m_{p} / n_{p}$ et $m'_{p} / n'_{p}$ sont voisines de Farey on a :

\begin{matrix} (m'_{p} + n'_{p}) (a n_{p} - b m_{p}) + (m_{p} + n_{p}) (b m'_{p} - a n'_{p}) & = a m'_{p} n_{p} + a n_{p} n'_{p} - b m_{p} m'_{p} - b m_{p} n'_{p} + b m_{p} m'_{p} + b m'_{p} n_{p} - a m_{p} n'_{p} - a n_{p} n'_{p} \\ = a (m'_{p} n_{p} - m_{p} n'_{p}) + b (m'_{p} n_{p} - m_{p} n'_{p}) \\ = a + b \end{matrix}

Par conséquent on a finalement : $a + b \geq m'_{p} + n'_{p} + m_{p} + n_{p}$ .

La suite d'entiers $(m'_{p} + n'_{p} + m_{p} + n_{p})$ est donc majorée par $a + b$ . Elle ne peut donc être strictement croissante mais elle est croissante car somme de quatre suites croissantes, donc il existe un rang p à partir duquel elle est stationnaire. Mais alors on doit avoir $m_{p} / n_{p} = m'_{p} / n'_{p} = a / b$ sinon on aurait $m_{p} / n_{p} < a / b < m'_{p} / n'_{p}$ et par définition l'un au moins (possiblement les deux) de $m_{p + 1} / n_{p + 1}$ ou de $m'_{p + 1} / n'_{p + 1}$ serait égal à la médiane $(m_{p} + m_{p + 1}) / (n_{p} + n_{p + 1})$ si bien que la somme $m_{p + 1} + m'_{p + 1} + n_{p + 1} + n'_{p + 1}$ serait strictement plus grande que $m_{p} + m'_{p} + n_{p} + n'_{p}$ , contredisant la stationnarité de la suite à partir de p.

Comparaison avec l'algorithme d'Euclide

L'algorithme d'Euclide permet de montrer la présence d'une fraction dans l'arbre en partant de celle-ci et par divisions euclidiennes successives de remonter vers la racine, construisant donc un chemin remontant de la fraction à la racine. La démonstration ci-dessus procède dans l'autre sens : partant de la racine on produit une suite de fractions qui se termine ultimement sur celle donnée initialement, produisant un chemin qui descend de la racine vers celle-ci. Noter que le même algorithme appliqué à un nombre réel plutôt qu'à une fraction permet de construire la branche infinie de fractions approximant ce réel. Modèle:Démonstration/fin

Fractions continues

Toute fraction admet un développement en fraction continue fini dont les coefficients sont les quotients successifs calculés par l'algorithme d'Euclide. Le même algorithme d'Euclide permettant de retrouver le chemin menant de la racine de l'arbre de Stern-Brocot à une fraction donnée, on peut en déduire que le développement en fraction continue code ce chemin. Précisément si Modèle:Math est le développement en fraction continue de la fraction Modèle:Math, les deux filles de Modèle:Math dans l'arbre de Stern-Brocot ont pour développement en fraction continue :

On en déduit par récurrence que la fraction Modèle:Math apparaît à l'étage Modèle:Math et que la suite Modèle:Math décrit le chemin y menant depuis la racine Modèle:Math : descendre Modèle:Math pas vers la droite, puis Modèle:Math pas vers la gauche, etc. jusqu'à Modèle:Math pas vers la gauche si Modèle:Math est pair, vers la droite si Modèle:Math est impair.

Autrement dit le chemin menant à la fraction de développement Modèle:Math est codé par le mot Modèle:Math où Modèle:Math est le symbole Modèle:Math si Modèle:Math est pair, Modèle:Math si Modèle:Math est impair.

Par exemple le développement en fraction continue de 2/5 est Modèle:Math ce qui correspond au chemin Modèle:Math : 0 pas à droite, puis 2 pas à gauche, puis un pas à droite. On pourra de même calculer que le développement en fraction continue de 17/12 est Modèle:Math tandis que le chemin dans l'arbre menant à 17/12 est représenté par le mot Modèle:Math.

Modèle:Démonstration/début

Appelons hauteur de $m / n$ le nombre $N = q_{1} + \dots + q_{p}$ . On suppose par récurrence que toute fraction de hauteur inférieure ou égale à $N$ apparaît à l'étage $N$ dans l'arbre de Stern-Brocot. On remarque tout d'abord que les deux filles présumées de $m / n$ sont de hauteur $N + 1$ et comme elles apparaissent à l'étage $N + 1$ (leur mère étant à l'étage $N$ ), on a bien démontré par récurrence l'égalité entre hauteur et étage de l'arbre.

Reste à démontrer que ces deux fractions sont bien les filles de $m / n$ . Pour cela on va trouver les deux voisines de $m / n$ dans la liste associée à l'étage $N$ .

Commençons par deux rappels préliminaires. Parmi les propriétés des voisinages de Farey il y a en particulier le fait que lorsque $a / b$ et $a^{'} / b^{'}$ sont voisines de Farey alors toute fraction $a^{″} / b^{″}$ située strictement entre les deux est obtenue en itérant l'opération de médiane à partir de $a / b$ et $a^{'} / b^{'}$ , donc apparaît forcément à un étage supérieur aux deux dans l'arbre de Stern-Brocot.

D'autre part si $[q_{1}; q_{2}, \dots, q_{p}]$ est une fraction continue, ses réduites $m_{k} / n_{k} = [q_{1}; q_{2}, . . ., q_{k}]$ pour $k = 1, \dots, p$ sont données par la récurrence :

$m_{- 1} = 0$ , $m_{0} = 1$ , $n_{- 1} = 1$ , $n_{0} = 0$ ;
$m_{k + 1} = m_{k} q_{k + 1} + m_{k - 1}$ , $n_{k + 1} = n_{k} q_{k + 1} + n_{k - 1}$ .

En particulier, comme $m / n = [q_{1}, \dots, q_{p} + 1]$ on a

\frac{m}{n} = \frac{m_{p - 1} (q_{p} + 1) + m_{p - 2}}{n_{p - 1} (q_{p} + 1) + n_{p - 2}} = \frac{m_{p - 1} q_{p} + m_{p - 2} + m_{p - 1}}{n_{p - 1} q_{p} + n_{p - 2} + n_{p - 1}} = \frac{m_{p} + m_{p - 1}}{n_{p} + n_{p - 1}}

Considérons la fraction continue $m^{'} / n^{'} = [q_{1}, \dots, q_{n - 1}] = m_{p - 1} / n_{p - 1}$ . Celle-ci est une voisine de Farey de $m / n$ . En effet on peut faire le calcul suivant :

\begin{matrix} m_{k + 1} n_{k} - m_{k} n_{k + 1} & = (m_{k} q_{k + 1} + m_{k - 1}) n_{k} - m_{k} (n_{k} q_{k + 1} + n_{k - 1}) \\ = - (m_{k} n_{k - 1} - m_{k - 1} n_{k}) \end{matrix}

d'où l'on déduit par récurrence que $m_{k + 1} n_{k} - m_{k} n_{k + 1} = (- 1)^{k + 1}$ et donc que $m_{k} / n_{k} = [q_{1}, \dots, q_{k}]$ et $m_{k + 1} / n_{k + 1} = [q_{1}, \dots, q_{k + 1}]$ sont voisines de Farey pour $k = 1, \dots, p$ . Autrement dit les réduites de deux fractions continues dont la première est un préfixe de la seconde et dont les longueurs diffèrent de 1 sont voisines de Farey. Par conséquent $m / n = [q_{1}, \dots, q_{p} + 1]$ et $m^{'} / n^{'} = [q_{1}, \dots, q_{p - 1}]$ sont voisines de Farey. Or $m / n$ est de hauteur $N$ tandis que $m^{'} / n^{'}$ est de hauteur $N^{'} = q_{1} + \dots q_{p - 1} - 1 < N$ , par hypothèse de récurrence $m^{'} / n^{'}$ est à l'étage $N^{'}$ , donc toutes deux sont dans la liste associée à l'étage $N$ , et sont donc consécutives dans celle-ci.

On en déduit que l'une des deux filles de $m / n$ à l'étage $N + 1$ est leur médiane:

\begin{matrix} \frac{m + m^{'}}{n + n^{'}} & = \frac{m_{p - 1} (q_{p} + 1) + m_{p - 2} + m_{p - 1}}{n_{p - 1} (q_{p} + 1) + n_{p - 2} + n_{p - 1}} \\ = \frac{m_{p - 1} (q_{p} + 2) + m_{p - 2}}{n_{p - 1} (q_{p} + 2) + n_{p - 2}} \end{matrix}

qui est la réduite de la fraction continue $[q_{1}, \dots, q_{p} + 2]$ comme attendu.

Considérons maintenant la fraction $m^{″} / n^{″} = [q_{1}, \dots, q_{p}] = m_{p} / n_{p}$ . Alors on a:

\begin{matrix} m^{″} n - m n^{″} & = m_{p} (n_{p} + n_{p - 1}) - (m_{p} + m_{p - 1}) n_{p} \\ = m_{p} n_{p - 1} - m_{p - 1} n_{p} \\ = (- 1)^{p} \end{matrix}

si bien que à nouveau $m^{″} / n^{″}$ et $m / n$ sont voisines de Farey. Mais $m^{″} / n^{″}$ est de hauteur $N^{″} = q_{1} + \dots + q_{p} - 1 = N - 1$ donc par récurrence, $m^{″} / n^{″}$ est à l'étage $N - 1$ , donc est voisine de $m / n$ dans la liste associée à l'étage $N$ . Par conséquent l'autre fille de $m / n$ est leur médiane:

\begin{matrix} \frac{m + m^{″}}{n + n^{″}} & = \frac{m_{p} + m_{p - 1} + m_{p}}{n_{p} + n_{p - 1} + n_{p}} \\ = \frac{2 m_{p} + m_{p - 1}}{2 n_{p} + n_{p - 1}} \end{matrix}

qui est la réduite de la fraction continue $[q_{1}, \dots, q_{p}, 2]$ comme annoncé. Modèle:Démonstration/fin

Cette correspondance entre fractions continues et arbre de Stern-Brocot est à la base de la définition de la fonction ? de Minkowski^[1] : informellement, celle-ci fait correspondre le réel associé à une branche du sous-arbre de l'arbre de Stern-Brocot enraciné en Modèle:Math (vue comme un développement en fraction continue infini d'un réel plus petit que 1) au réel associé à cette même branche mais dans l'arbre dyadique, c'est-à-dire au réel dont le développement en base 2, vu comme une suite infinie de 0 et de 1, code la branche.

Dans le cas d'une fraction plus petite que 1, dont le développement en fraction continue est donc de la forme Modèle:Math, la fonction ? considère le chemin en partant de la fraction Modèle:Math qui est donc codé par la suite Modèle:Math et lui associe le rationnel dyadique figurant à la même position dans l'arbre dyadique ; celui-ci se calcule en considérant le mot Modèle:Math codant le chemin, en lui ajoutant un 1 à la fin, ce qui donne Modèle:Math et en lisant le mot obtenu comme le développement en base 2 d'un rationnel dyadique.

Par exemple Modèle:Math a pour développement Modèle:Math. Le chemin y menant depuis la fraction Modèle:Math est donc codé par la suite Modèle:Math ce qui donne le mot binaire Modèle:Math. Ce mot se lit comme le développement binaire du rationnel dyadique Modèle:Math. De même Modèle:Math a pour développement Modèle:Math, donc son chemin depuis Modèle:Math est codé par la suite Modèle:Math, d'où le mot binaire Modèle:Math ce qui donne finalement le développement binaire Modèle:Math.

Algorithme matriciel

On donne ici une méthode utilisant le calcul matriciel pour déterminer une fraction connaissant sa position dans l'arbre de Stern-Brocot qui est une variante du calcul des réduites de son développement en fraction continue. Pour la lisibilité dans cette section on va coder les chemins comme des mots sur l'alphabet composé des deux lettre G (pour les déplacements à gauche) et D (pour les déplacements à droite).

Soit donc un mot S composé de G et de D, on définit f(S) comme la fraction correspondant à S, c'est-à-dire la fraction atteinte en partant de la racine et en suivant le chemin codé par S. Par exemple si S = GGD alors f(S) = 2/5.

On ne considère que des matrices 2x2, ou des matrices colonnes 1x2. Étant donné une matrice colonne $(\begin{matrix} m \\ n \end{matrix})$ on note $q (\begin{matrix} m \\ n \end{matrix})$ le rationnel $\frac{m}{n}$ . Si $V_{1}$ et $V_{2}$ sont deux matrices colonnes, leur médiane est $V_{1} + V_{2}$ ; la terminologie est justifiée par le fait que la fraction $q (V_{1} + V_{2})$ est la médiane au sens défini plus haut des fractions $q (V_{1})$ et $q (V_{2})$ .

On remarque que la médiane de $V_{1}$ et $V_{2}$ s'obtient en appliquant la matrice $(\begin{matrix} V_{1} & V_{2} \end{matrix})$ constituée des deux blocs $V_{1}$ et $V_{2}$ à la matrice colonne $(\begin{matrix} 1 \\ 1 \end{matrix})$ ; et comme $V_{1} + V_{2} = V_{2} + V_{1}$ on obtient le même résultat avec la matrice blocs $(\begin{matrix} V_{2} & V_{1} \end{matrix})$ . En résumé :

V_{1} + V_{2} = (\begin{matrix} V_{1} & V_{2} \end{matrix}) (\begin{matrix} 1 \\ 1 \end{matrix}) = (\begin{matrix} V_{2} & V_{1} \end{matrix}) (\begin{matrix} 1 \\ 1 \end{matrix})

.

Par définition de l'arbre de Stern-Brocot, chaque fraction $q (V)$ y apparaît comme la médiane de deux fractions $q (P_{1})$ et $q (P_{2})$ dont l'une est située à l'étage immédiatement au-dessus. L'idée de l'algorithme matriciel est de calculer $P_{1}$ et $P_{2}$ plutôt que $V$ ; plus précisément on va calculer la matrice $(\begin{matrix} P_{2} & P_{1} \end{matrix})$ . On en déduit $V$ puisque l'on vient de voir que $V = (\begin{matrix} P_{2} & P_{1} \end{matrix}) (\begin{matrix} 1 \\ 1 \end{matrix})$ .

Pour cela on remarque que si $q (V)$ est obtenue comme médiane de $q (P_{1})$ et $q (P_{2})$ , alors les deux filles gauche et droite de $q (V)$ sont respectivement les médianes de $q (P_{1})$ et $q (V)$ et de $q (V)$ et $q (P_{2})$ . Autrement dit on passe de la matrice $(\begin{matrix} P_{2} & P_{1} \end{matrix})$ associée à $V = P_{1} + P_{2}$ aux matrices $(\begin{matrix} P_{1} + P_{2} & P_{1} \end{matrix})$ associée à sa fille gauche, et $(\begin{matrix} P_{2} & P_{1} + P_{2} \end{matrix})$ associée à sa fille droite.

Ceci conduit à définir $\hat{G} = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}), \hat{D} = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ puisque alors on a : $(\begin{matrix} P_{2} & P_{1} \end{matrix}) \hat{G} = (\begin{matrix} P_{2} + P_{1} & P_{1} \end{matrix})$ et $(\begin{matrix} P_{2} & P_{1} \end{matrix}) \hat{D} = (\begin{matrix} P_{2} & P_{2} + P_{1} \end{matrix})$ .

Ainsi on a défini les matrices correspondant aux deux descentes gauche et droite d'une mère vers sa fille ; reste à itérer le procédé le long du chemin S (on dit que l'on fait agir le monoïde des mots sur les matrices) par la définition récursive :

si $S = ϵ$ est le mot vide (représentant le chemin de la racine à elle-même) alors $\hat{S} = \hat{ϵ} = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$ ;
si $S = T G$ représente un chemin se terminant par un mouvement gauche, alors $\hat{S} = \hat{T} \hat{G}$ ;
si $S = T D$ représente un chemin se terminant par un mouvement droit, alors $\hat{S} = \hat{T} \hat{D}$ .

Notons que la matrice $\hat{ϵ}$ est de la forme $(\begin{matrix} V_{2} & V_{1} \end{matrix})$ où $V_{1} = (\begin{matrix} 0 \\ 1 \end{matrix})$ et $V_{2} = (\begin{matrix} 1 \\ 0 \end{matrix})$ sont les deux matrices colonnes correspondant aux 2 fractions 0/1 et 1/0, dont la médiane est la racine de l'arbre de Stern-Brocot. Ainsi la matrice associé au chemin vide permet bien de calculer la fraction associée au chemin vide, à savoir la racine de l'arbre. On remarque que $\hat{ϵ}$ est la matrice identité ; c'est pour obtenir cette simplification que l'on a renversé l'ordre des matrices, préférant calculer $(\begin{matrix} P_{2} & P_{1} \end{matrix})$ plutôt que $(\begin{matrix} P_{2} & P_{1} \end{matrix})$ .

Ainsi si $S$ est le mot $S_{1} S_{2} \dots S_{n}$ où les $S_{i}$ sont G ou D alors $\hat{S}$ est la matrice $\hat{ϵ} {\hat{S}}_{1} \dots {\hat{S}}_{n} = {\hat{S}}_{1} \dots {\hat{S}}_{n}$ .

On obtient ainsi une façon très agréable de calculer notre fraction $f (S)$ :

f (S) = q ({\hat{S}}_{1} {\hat{S}}_{2} \dots {\hat{S}}_{n} (\begin{matrix} 1 \\ 1 \end{matrix}))

.

Ainsi sur l'exemple $S = G G D$ du chemin menant à la fraction 2/5 on a :

$\hat{S} = \hat{G} \hat{G} \hat{D} = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}) = (\begin{matrix} 1 & 1 \\ 2 & 3 \end{matrix})$ si bien que finalement $\hat{S} (\begin{matrix} 1 \\ 1 \end{matrix}) = (\begin{matrix} 2 \\ 5 \end{matrix})$ comme attendu.

Voir aussi

Articles connexes

Liens externes

Modèle:Article

Références

Modèle:Références

Mathématiques concrètes (Modèle:2e) de Ronald Graham, Donald Knuth et Oren Patashnik Modèle:ISBN

Modèle:Portail

↑ Modèle:Lien web

[1] Modèle:Lien web

[1]

Arbre de Stern-Brocot

Sommaire

Construction

Exemple : les premiers étages de l'arbre

Propriétés élémentaires : lien avec les suites de Farey

Arbre de Stern-Brocot et algorithme d'Euclide

Énumération des rationnels

Fractions continues

Algorithme matriciel

Voir aussi

Articles connexes

Liens externes

Références

Menu de navigation

Arbre de Stern-Brocot

Construction

Exemple : les premiers étages de l'arbre

Propriétés élémentaires : lien avec les suites de Farey

Arbre de Stern-Brocot et algorithme d'Euclide

Énumération des rationnels

Fractions continues

Algorithme matriciel

Voir aussi

Articles connexes

Liens externes

Références

Menu de navigation

Rechercher