Suite diatomique de Stern

En mathématiques, la suite diatomique de Stern, ou suite de Stern-Brocot, est une suite d'entiers naturels introduite par le mathématicien Moritz Stern en 1858^[1], et dont les premiers termes sont :

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

Cette suite, notée $({\rm {fusc}}(n))$ est définie par récurrence de la façon suivante :

${\rm {fusc}}(0)=0,{\rm {fusc}}(1)=1$
${\begin{cases}{\rm {fusc}}(2n)={\rm {fusc}}(n)\\{\rm {fusc}}(2n+1)={\rm {fusc}}(n)+{\rm {fusc}}(n+1)\end{cases}}$

L'appellation "fusc" a été donnée, sans explication, par Edsger W. Dijkstra en 1976 ^[2]^,^[3].

Un définition par récurrence double, proche de celle de la suite de Fibonacci, est, avec la même initialisation :

${\rm {fusc}}(n+2)={\rm {fusc}}(n+1)+{\rm {fusc}}(n)-2({\rm {fusc}}(n){\text{ mod }}{\rm {fusc}}(n+1))$ ^[4]

où $a{\text{ mod }}b$ est le reste de la division euclidienne de $a$ par $b$ .

On peut construire la suite ligne par ligne en procédant selon la figure ci-contre. Omettant le premier terme 0, on part de la ligne 1 - 1. Puis chaque nouvelle ligne est recopiée de la ligne précédente en insérant des nombres, chaque nouveau nombre étant la somme des deux nombres situés de part et d'autre de sa position dans la ligne précédente.

Propriétés

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 : $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^[5] :

${\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 $n=13=2^{3}+2^{2}+2^{0}$ , la matrice est ${\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.

Structure fractale

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.

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

Série génératrice

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

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 :

n=e_{0}+2e_{1}+4e_{2}+8e_{3}+\dots

où les

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

Dénombrement

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

fusc(n) est le nombre de sous-suites^[7] 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 $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 les nombres de Stirling de deuxième espèce $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$ sont eux-mêmes impairs^[8]. Par exemple, les nombres de Stirling vérifiant cette propriété pour n = 9 sont successivement 1, 3025, 6951, 1, et fusc(9) = 4.

Suite de Stern et nombres rationnels

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^[9] :

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

Les premières images de cette fonction sont :

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.

Suite de Stern et fonction ?( ) de Minkowski

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

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.

Détenteurs de record pour la suite de Stern

Ali Keramatipour et Jeffrey Shallit considèrent ce qu'ils appellent des « détenteurs de record » (« record-setter » en anglais) dans la suite de Stern^[10].

Un « détenteurs de record » pour une suite d'entiers $(s(n))_{n\geq 0}$ est un indice $m$ tel que $s(i)<s(m$ ) pour tout $i<m$ , donc ce terme est plus grand que tous ceux qui le précèdent. La suite des détenteurs commence par :

1, 3, 5, 9, 11, 19, 21, 35, 37, 43, 69, 73, 75, 83, 85, 139, 147, 149, 165,... (suite A212288 de l'OEIS)

En effet, dans la suite de Stern

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ...

les valeurs des détenteurs de record successifs soulignés ci-dessus se trouvent aux positions indiquées.

Les auteurs donnent une description explicite (même si elle est compliquée) de valeurs de cette suite.

Enfin, la suite des maxima dans la suite de Stern qui est la suite :

0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 7 (suite A270362 de l'OEIS)

n'est pas une suite 2-automatique^[10].

Références

↑ M. A. Stern, Über einse zahlentheoretische Function, J. Reine Agnew. Math., 55, (1858), 193-220
↑ (en) E. W. Dijkstra, « An exercise for Dr.R.M.Burstall », 1976
↑ (en) E. W. Dijkstra, « More about the function “fusc” (A sequel to EWD570) », 1976
↑ Jean-Paul DELAHAYE, « La suite de Stern-Brocot, sœur de Fibonacci », Pour la Science, n^o 420,‎ octobre 2012 (lire en ligne)
↑ Valerio De Angelis, « The Stern Diatomic Sequence via the Generalised Chebyshev Polynomials », Amer. Math. monthly, vol. 124, n^o 5,‎ mai 2017, p. 451-455. La démonstration consiste à vérifier que le déterminant et la suite de Stern vérifie des relations de récurrence identiques.
↑ Richard P. Stanley, « Some Linear Recurrences Motivated by Stern's Diatomic Array », Amer. Math. Monthly, vol. 127, n^o 2,‎ février 2020, p. 100
↑ S. R. Finch, Mathematical constants, Encyclopedia of mathematics and its applications, vol.94 Cambridge University Press, (2003)
↑ L. Carlitz, A problem in partitions related to the Stirling numbers, Bull. Amer. Math. Soc., 70, (1964), 275-278
↑ Neil Calkin, Herbert S. Wilf, « Recounting the Rationals », Amer. Math. Monthly, vol. 107, n^o 4,‎ avril 2000, p. 360-363 (lire en ligne)
↑ ^{a et b} Keramatipour et Shallit 2024.

Bibliographie

Robert Ferréol, « Addition des cancres, suites de Brocot et friandises associées », Quadrature, n^o 36,‎ avril mai juin 1999, p. 13 - 24 (lire en ligne)
Roger Mansuy, « Achille Brocot, mathématicien à ses heures », sur CultureMATH, 20 mai 2008
Sam Northshield, Stern's diatomic sequence, American Math. Monthly, 117, (août-septembre 2010), 581-598
Jean-Paul Delahaye, « Mathématique des engrenages », Pour La Science, n^o 537,‎ juillet 2022, p. 84 (lire en ligne )
Ali Keramatipour et Jeffrey Shallit, « Record-setters in the Stern sequence », Discrete Mathematics, vol. 347, n^o 4,‎ 1^er avril 2024, article n^o 113852 (DOI 10.1016/j.disc.2023.113852, arXiv 2205.06223).

Articles connexes

Portail des mathématiques

[1] M. A. Stern, Über einse zahlentheoretische Function, J. Reine Agnew. Math., 55, (1858), 193-220

[2] (en) E. W. Dijkstra, « An exercise for Dr.R.M.Burstall », 1976

[3] (en) E. W. Dijkstra, « More about the function “fusc” (A sequel to EWD570) », 1976

[4] Jean-Paul DELAHAYE, « La suite de Stern-Brocot, sœur de Fibonacci », Pour la Science, n^o 420,‎ octobre 2012 (lire en ligne)

[5] Valerio De Angelis, « The Stern Diatomic Sequence via the Generalised Chebyshev Polynomials », Amer. Math. monthly, vol. 124, n^o 5,‎ mai 2017, p. 451-455. La démonstration consiste à vérifier que le déterminant et la suite de Stern vérifie des relations de récurrence identiques.

[6] Richard P. Stanley, « Some Linear Recurrences Motivated by Stern's Diatomic Array », Amer. Math. Monthly, vol. 127, n^o 2,‎ février 2020, p. 100

[7] S. R. Finch, Mathematical constants, Encyclopedia of mathematics and its applications, vol.94 Cambridge University Press, (2003)

[8] L. Carlitz, A problem in partitions related to the Stirling numbers, Bull. Amer. Math. Soc., 70, (1964), 275-278

[9] Neil Calkin, Herbert S. Wilf, « Recounting the Rationals », Amer. Math. Monthly, vol. 107, n^o 4,‎ avril 2000, p. 360-363 (lire en ligne)

[KS-10] {a et b} Keramatipour et Shallit 2024.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]