Suite diatomique de Stern

Suite de Stern, disposée ligne par ligne. Chaque colonne forme alors une suite arithmétique, les raisons (indiquées en bleu) étant les termes mêmes de la suite de Stern.

Si l'on dispose la suite de Stern en lignes successives de 1, 2, 4, 8, ... termes, comme dans la figure ci-contre, il apparait des propriétés remarquables.

• La somme des termes de chaque ligne est une puissance de 3.
• Les maximums de chaque ligne constituent la suite de Fibonacci.
• Si on omet le 1 initial, chaque ligne est un palindrome.

• Chaque colonne forme une suite arithmétique. La suite formée des raisons est la suite de Stern elle-même. Cela signifie que la suite de Stern dispose d'une structure fractale.

Si l'on décompose l'entier n en binaire : ${\displaystyle n=2^{d_{r}}+2^{d_{r-1}}+\dots +2^{d_{0}}}$, les puissances étant décroissantes, alors fusc(n) est égal au déterminant de la matrice tridiagonale[4] :

${\displaystyle {\begin{pmatrix}d_{r}-d_{r-1}+1&1&0&0&\dots &0\\1&d_{r-1}-d_{r-2}+1&1&0&\dots &0\\\vdots &&&\dots &&\vdots \\0&\dots &0&1&d_{2}-d_{1}+1&1\\0&\dots &0&0&1&d_{1}-d_{0}+1\\\end{pmatrix}}}$

Par exemple, pour ${\displaystyle n=13=2^{3}+2^{2}+2^{0}}$, la matrice est ${\displaystyle {\begin{pmatrix}2&1\\1&3\end{pmatrix}}}$, de déterminant fusc(13)=5. Cette propriété permet de montrer que l'entier m obtenu à partir de n en inversant l'ordre de ses chiffres binaires a même image que n par fusc. Ainsi, pour n = 13 = 0b1101, on a m=0b1011 = 11 et fusc(11) = 5.

La suite de Stern apparaît quand on compte le nombre de coefficients impairs des diagonales ascendantes du triangle de Pascal.

La structure fractale de la suite apparaît également en liaison avec le triangle de Sierpiński. Ce dernier peut se remplir par étape à partir du triangle de Pascal en noircissant les nombres impairs et en blanchissant les nombres pairs. Si on compte les nombres impairs le long des diagonales ascendantes du triangle de Pascal, on obtient la suite de Stern. Dans la figure ci-contre, les nombres impairs ont été remplacés par des 1 et les nombres pairs par des 0. Ce procédé est comparable à l'obtention des termes de la suite de Fibonacci en sommant les termes des diagonales ascendantes du triangle de Pascal.

Représentation graphique des points (n, fusc(n)) de la suite de Stern.

On peut enfin visualiser cet aspect en représentant graphiquement les points (n,fusc(n)) de la suite.

La série génératrice ${\displaystyle G(x)=\sum _{n=0}^{\infty }{\rm {fusc}}(n)x^{n}}$ de la suite de Stern est égale à[5] :

${\displaystyle G(x)=x\prod _{n=0}^{\infty }\left(1+x^{2^{n}}+x^{2^{n+1}}\right)}$

Si on développe cette fonction, on montre que fusc(n+1) est égal au nombre de façons de décomposer n comme somme de puissances de 2 sous la forme suivante, généralisant la notation en système binaire :

${\displaystyle n=e_{0}+2e_{1}+4e_{2}+8e_{3}+\dots }$ où les ${\displaystyle e_{i}}$ valent 0, 1, ou 2.

Par exemple, pour n = 18, fusc(19) = 7, et 18 possède 7 décompositions, à savoir :

18 = 2 + 16 = 1 + 1 + 16 = 2 + 8 + 8 = 1 + 1 + 8 + 8 = 2 + 4 + 4 + 8 = 1 + 1 + 4 + 4 + 8 = 1 + 1 + 2 + 2 + 4 + 8

La suite de Stern intervient dans plusieurs problèmes de dénombrement.

• fusc(n) est le nombre de sous-suites[6] de la forme 1010...101 (avec une alternance de 1 et de 0, commençant et se terminant par 1, limitée éventuellement à un seul 1) extraites de la suite constituant la décomposition de n en base 2. Par exemple ${\displaystyle 19=10011_{b}}$ en binaire, et il y a fusc(19) = 7 sous-suites possibles, à savoir 4 suites de la forme 101 et 3 suites limitées à 1.

• fusc(n) est le nombre de valeurs impaires k pour lesquelles le nombre de Stirling de deuxième espèce ${\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}}$ est lui-même impair[7]. Par exemple, les nombres de Stirling vérifiant cette propriété pour n = 9 sont 1, 3025, 6951, 1, et fusc(9) = 4.

La suite de Stern permet d'établir une bijection entre les entiers positifs ou nuls et les nombres rationnels positifs ou nuls au moyen de l'application[8] :

${\displaystyle n\in \mathbb {N} \rightarrow {\frac {{\rm {fusc}}(n)}{{\rm {fusc}}(n+1)}}\in \mathbb {Q} ^{+}}$

Les premières images de cette fonction sont :

${\displaystyle 0,1,{\frac {1}{2}},2,{\frac {1}{3}},{\frac {3}{2}},{\frac {2}{3}},3,{\frac {1}{4}},{\frac {4}{3}},{\frac {3}{5}},\dots }$

Le nombre fusc(n) / fusc(n + 1) est en effet le n-ième nombre rationnel du parcours en largeur de l'arbre de Calkin-Wilf, qui établit une telle bijection.

La suite de Stern apparaît aussi dans les numérateurs et dénominateurs des fractions construites au moyen de l'arbre de Stern-Brocot, et qui établit également une bijection entre les entiers positifs ou nuls et les rationnels positifs ou nuls.

Considérons la fonction f suivante, définie sur les nombres dyadiques :

${\displaystyle f\left({\frac {k}{2^{n}}}\right)={\frac {{\rm {fusc}}(k)}{{\rm {fusc}}(2^{n}+k)}},k\leq 2^{n}}$

Cette fonction se prolonge sur [0,1] en une fonction continue strictement croissante, bijective de [0,1] sur [0,1], appelée fonction boîte de Conway. La réciproque de cette extension est la fonction point d'interrogation de Minkowski.