Suite diatomique de Stern

Suite d'entiers naturels

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 :

Construction de la suite de Stern. La suite s'obtient en lisant chaque ligne successivement de gauche à droite. Les 1 de la colonne de droite sont à identifier avec les 1 de la colonne de gauche et ne sont pas pris en compte dans la liste des éléments de la suite.
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 est définie par récurrence de la façon suivante :

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 :

  • [4]

est le reste de la division euclidienne de par .

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

modifier
 
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 :  , les puissances étant décroissantes, alors fusc(n) est égal au déterminant de la matrice tridiagonale[5] :

 

Par exemple, pour  , la matrice est  , 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

modifier
 
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.

Série génératrice

modifier

La série génératrice   de la suite de Stern est égale à[6] :

 

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 :

  où les   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

modifier

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   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   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

modifier

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] :

 

Les premières images de cette fonction sont :

 

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

modifier

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

 

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

modifier

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   est un indice   tel que  ) pour tout  , 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

modifier
  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 »,
  3. (en) E. W. Dijkstra, « More about the function “fusc” (A sequel to EWD570) »,
  4. Jean-Paul DELAHAYE, « La suite de Stern-Brocot, sœur de Fibonacci », Pour la Science, no 420,‎ (lire en ligne)
  5. Valerio De Angelis, « The Stern Diatomic Sequence via the Generalised Chebyshev Polynomials », Amer. Math. monthly, vol. 124, no 5,‎ , 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, no 2,‎ , 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, no 4,‎ , p. 360-363 (lire en ligne)
  10. a et b Keramatipour et Shallit 2024.

Bibliographie

modifier

Articles connexes

modifier