Arbre de Calkin-Wilf
# Arbre de Calkin-Wilf

En théorie des nombres et en combinatoire, l'arbre de Calkin-Wilf, est un arbre dont les sommets sont en bijection avec les nombres rationnels positifs. L'arbre a pour racine le nombre 1, et tout nombre rationnel positif, exprimé sous la forme d'une fraction réduite a/b, a deux enfants qui correspondent aux nombres a/(a + b) et (a + b)/b. Chaque nombre rationnel positif figure exactement une fois dans l’arbre.

La suite de nombres rationnels obtenue par un parcours en largeur de l'arbre de Calkin-Wilf est connue sous le nom de suite de Calkin-Wilf. La suite des numérateurs (ou la suite des dénominateurs décalée d'un terme) est la suite diatomique de Stern, et peut être calculée par la fonction fusc.

## Historique

L'arbre de Calkin-Wilf porte le nom de Neil Calkin (en) et Herbert Wilf qui l'ont étudié dans un article commun paru en 2000. L'arbre a été introduit auparavant par Jean Berstel et Aldo de Luca sous le nom de Raney tree, parce qu'ils ont repris des concepts d'un article de George N. Raney. La suite diatomique de Stern a été décrite bien plus tôt par Moritz Abraham Stern, mathématicien allemand du XIXe siècle qui est aussi l'inventeur de l'arbre de Stern-Brocot.

Et même encore plus tôt, un arbre semblable (incluant seulement les fractions entre 0 et 1) apparaît chez Johannes Kepler dans son Harmonices Mundi (1619).

## Définition et structure

On peut définir l’arbre de Calkin-Wilf comme étant un graphe orienté, où chaque nombre rationnel positif $a/b$ figure comme sommet et possède, à l'exception du sommet 1, un arc sortant unique vers un autre sommet appelé son sommet parent. On suppose que la fraction $a/b$ est réduite, en d'autres termes que le plus grand commun diviseur de a et b est 1. Si $a/b<1$, le parent de $a/b$ est $a/(b-a)$ ; si $a/b>1$, le parent de $a/b$ est $(a-b)/b$. Dans les deux cas, le parent est une fraction dont la somme du numérateur et du dénominateur est plus petite; de sorte que la répétition de ces réductions amène finalement au nombre 1, sans parent, la racine. Il s'agit bien d'un arbre au sens de la théorie des graphes, avec un seul arc sortant par sommet et une racine accessible de tout sommet.

Les enfants d'un sommet de l'arbre de Calkin-Wilf se calculent en inversant les formules précédentes : chaque sommet a/b a un enfant de valeur $a/(a+b)$ plus petite que 1, et un enfant $(a+b)/b$ de valeur plus grande que 1. L'arbre de Calkin-Wilf est bien un arbre binaire, mais sans être un arbre binaire de recherche, car l'ordre obtenu par le parcours infixe ne correspond pas à l'ordre naturel des sommets. Il existe toutefois une relation étroite avec l'arbre de Stern-Brocot (qui est lui un arbre binaire de recherche) : les sommets des deux arbres sont les mêmes à chaque niveau, et ils sont liés par la permutation obtenue en renversant la représentation binaire de leur position, appelée en anglais la bit-reversal permutation (en).

## Parcours en largeur

La suite de Calkin–Wilf est la suite de nombres rationnels obtenue par un parcours en largeur de l'arbre de Calkin-Wilf. Ses premiers éléments sont :

    1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, ...

Comme l'arbre de Calkin-Wilf contient chaque nombre rationnel positif exactement une fois, il en est de même de cette suite. Le dénominateur de chaque fraction est égal au numérateur de la fraction suivante. La suite peut aussi être engendrée par la formule de récurrence :

    $q_{i+1}={\frac {1}{2\lfloor q_{i}\rfloor -q_{i}+1}}$

où $q_{i}$ est le i-ème nombre de la suite, avec $q_{1}=1$, et $\lfloor q_{i}\rfloor$ est la partie entière de $q_{i}$.

On peut aussi calculer $q_{i}$ directement à partir du run-length encoding de la représentation binaire de i : on compte le nombre de chiffres égaux à 1 à partir du bit de plus faible poids, puis le nombre de chiffres égaux à 0, puis à nouveau le nombre de chiffres égaux à 1 etc. La suite d'entiers positifs ainsi obtenue est la représentation en fraction continue de $q_{i}$.

### Exemples

   * pour $i=1081=10000111001_{2}$, la fraction continue obtenue est [1;2,3,4,1], et donc $q_{1081}=53/37$.

   * pour $i=1990=11111000110_{2}$, la fraction continue est [0;1,2,3,5], et $q_{1990}=37/53$

    Attention, la réciproque n'est pas toujours vraie, une fraction continue peut avoir une valeur binaire identique à une autre.
   * les fractions continues de $q_{i}=1/2$ et de $q_{j}=3/2$ sont respectivement [0, 2] et [1, 2], donc $i=011_{2}=3$ et $j=11_{2}=3$. Pour retrouver la position d'un nombre il faut absolument remonter vers la racine de l'arbre en ajoutant si le numérateur est supérieur au dénominateur 1 à l'avant du résultat binaire et 0 sinon.

    var p = parseInt(n); // numérateur var q = parseInt(d); // dénominateur var bits = ""; while (!(p == 1 && q == 1)) { // tant qu'on est pas à la racine if (p > q) { bits = "1" + bits; p = p - q; } else { bits = "0" + bits; q = q - p; } } bits = "1" + bits; // le bit de la racine var resultat = parseInt(bits, 2);

Une conversion similaire entre développements binaires codés en run-length encoding et fractions continues peut être utilisée pour évaluer la fonction point d'interrogation de Minkowski ; dans l'arbre de Calkin–Wilf, les nombres binaires sont des entiers, à savoir les positions dans le parcours en largeur, alors que dans la fonction point d'interrogation ce sont des nombres réels entre 0 et 1.

## Suite diatomique de Stern

La suite diatomique de Stern est la suite d'entiers

    0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... (suite A002487 de l'OEIS).

Si on numérote les éléments à partir de 0, la valeur du n-ième de la suite est la valeur fusc(n) de la fonction fusc, fonction définie par la relation de récurrence

    $\operatorname {fusc} (2n)=\operatorname {fusc} (n)$
    $\operatorname {fusc} (2n+1)=\operatorname {fusc} (n)+\operatorname {fusc} (n+1)$

avec les conditions initiales

    $\operatorname {fusc} (0)=0$ et $\operatorname {fusc} (1)=1$.

Le n-ième nombre dans le parcours en profondeur de l'arbre de Calkin–Wilf est le nombre $\operatorname {fusc} (n)/\operatorname {fusc} (n+1)$. Ceci montre que la suite diatomique forme à la fois la suite des numérateurs et la suite des dénominateurs des nombres de la suite de Calkin–Wilf.

Le nombre fusc(n + 1) est aussi le nombre de coefficients binomiaux impairs de la forme

    ${n-r \choose r},\ 0\leqslant 2r<n$

et il compte également le nombre de façons d'écrire n comme une somme de puissances de deux où chaque puissance apparaît au plus deux fois. On peut voir cela à partir de la relation de récurrence qui définit fusc comme suit : les expressions comme somme de puissances de 2 pour un nombre pair 2n ou bien ne comportent pas de 1, (et dans ce cas elles sont formées en doublant chaque terme de l'expression pour n) ou bien comportent deux 1 (et dans ce cas le reste de l'expression est formé en doublant chaque terme de l'expression pour n - 1), de sorte que le nombre de représentants est la somme du nombre de représentations pour n et pour n - 1, en accord avec la relation de récurrence. De même, chaque représentation pour un nombre impair 2n + 1 est formé en doublant une représentation pour n et en ajoutant 1, à nouveau en accord avec la récurrence. Par exemple

    6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1

a trois représentations comme somme de puissances de deux ayant au plus deux occurrences de chaque puissance, de sorte que fusc(6 + 1) = 3.

## Rapport avec l'arbre de Stern–Brocot

L'arbre de Calkin–Wilf ressemble à l'arbre de Stern-Brocot, dans la mesure où les deux sont des arbres binaires contenant chaque nombre rationnel positif exactement une fois. De plus, les mêmes nombres apparaissent dans les deux arbres aux mêmes niveaux, mais pas dans le même ordre. Les arbres peuvent être obtenus l'un à partir de l’autre au moyen d'une bit-reversal permutation (en) appliquée à chaque niveau de l'arbre. On peut aussi transformer le nombre associé à un nœud donné de l'arbre de Calkin–Wilf en le nombre en même position dans l'arbre de Stern–Brocot et réciproquement par une méthode qui utilise le retournement de la représentation en fraction continue de ces nombres. Les deux arbres ont aussi des propriétés qui les distinguent : un arbre de Stern–Brocot est un arbre binaire de recherche, c'est-à-dire que le parcours infixe de gauche à droite donne les nombres en ordre numérique croissant, alors que l'arbre de Calkin–Wilf n'a pas cette propriété.

