Accueil🇫🇷Chercher

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

La n-ième valeur de cette suite est fusc(n), où la fonction fusc est définie par les relations de récurrence suivantes :

  • fusc(0) = 0
  • fusc(1) = 1
  • fusc(2n) = fusc(n)
  • fusc(2n + 1) = fusc(n) + fusc(n + 1)

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

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

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

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

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

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

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

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

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

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

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.

Voir aussi

Bibliographie

  • Robert Ferréol, « Addition des cancres, suites de Brocot et friandises associées », Quadrature, no 36, avril mai juin 1999, p. 13 - 24 (lire en ligne)
  • Roger Mansuy, « Achille Brocot, mathématicien à ses heures », sur CultureMATH,
  • Sam Northshield, Stern's diatomic sequence, American Math. Monthly, 117, (août-), 581-598
  • J.P. Delahaye, « Mathématique des engrenages », Pour La Science, no 537, , p. 84 (lire en ligne Accès payant)

Articles connexes

Références

  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. 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.
  5. Richard P. Stanley, « Some Linear Recurrences Motivated by Stern's Diatomic Array », Amer. Math. Monthly, vol. 127, no 2, , p. 100
  6. S. R. Finch, Mathematical constants, Encyclopedia of mathematics and its applications, vol.94 Cambridge University Press, (2003)
  7. L. Carlitz, A problem in partitions related to the Stirling numbers, Bull. Amer. Math. Soc., 70, (1964), 275-278
  8. Neil Calkin, Herbert S. Wilf, « Recounting the Rationals », Amer. Math. Monthly, , p. 360-363
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.