Suita diatomică a lui Stern

În matematică , secvența diatomică a lui Stern este o succesiune de numere naturale introduse de matematicianul Moritz Stern în 1858 și ai cărei primii termeni sunt:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... (continuare A002487 din OEIS ).

Valoarea a n- a acestei secvențe este fusc ( n ), unde funcția fusc este definită de următoarele relații de recurență :

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

Numele „fusc” a fost dat, fără explicații, de Edsger W. Dijkstra în 1976.

Putem construi secvența linie cu linie procedând conform figurii opuse. Omiind primul termen 0, începem de la linia 1 - 1. Apoi fiecare linie nouă este copiată de la linia anterioară prin inserarea numerelor, fiecare număr nou fiind suma celor două numere situate de ambele părți ale poziției sale în linia anterioară.

Proprietăți

Dacă avem secvența Stern în linii succesive de 1, 2, 4, 8, ... termeni, ca în figura opusă, apar câteva proprietăți remarcabile.

Suma termenilor din fiecare rând este o putere de 3.
Maximele fiecărei linii constituie secvența Fibonacci .
Dacă omitem 1 inițial, fiecare rând este un palindrom .

Fiecare coloană formează o secvență aritmetică . Secvența formată din motive este secvența Stern în sine. Aceasta înseamnă că suita Stern are o structură fractală .

Dacă descompunem întregul n în binar :, puterile fiind descrescătoare, atunci fusc ( n ) este egal cu determinantul matricei tridiagonale : ${\ displaystyle n = 2 ^ {d_ {r}} + 2 ^ {d_ {r-1}} + \ dots + 2 ^ {d_ {0}}}$

${\ 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 & \ puncte & 0 & 0 & 1 & d_ {1} -d_ {0} +1 \\\ end {pmatrix}}}$

De exemplu, pentru , matricea este , cu determinant fusc (13) = 5. Această proprietate face posibil să se arate că numărul întreg m obținut din n prin inversarea ordinii cifrelor sale binare are aceeași imagine ca n prin fusc. Astfel, pentru n = 13 = 0b1101, avem m = 0b1011 = 11 și fusc (11) = 5. ${\ displaystyle n = 13 = 2 ^ {3} + 2 ^ {2} + 2 ^ {0}}$ ${\ displaystyle {\ begin {pmatrix} 2 & 1 \\ 1 & 3 \ end {pmatrix}}}$

Structura fractală

Structura fractală a secvenței apare și în legătură cu triunghiul Sierpiński . Acesta din urmă poate fi completat pas cu pas din triunghiul lui Pascal prin întunecarea numerelor impare și albirea numerelor pare. Dacă numărăm numerele impare de-a lungul diagonalelor ascendente ale triunghiului lui Pascal, obținem secvența Stern. În figura opusă, numerele impare au fost înlocuite cu 1 și numerele pare cu 0. Acest proces este comparabil cu obținerea termenilor secvenței Fibonacci prin însumarea termenilor diagonalelor ascendente ale triunghiului lui Pascal.

Putem vizualiza în cele din urmă acest aspect reprezentând grafic punctele ( n , fusc ( n )) ale secvenței.

Seria generatorului

Seria generatoare a secvenței Stern este egală cu: ${\ displaystyle G (x) = \ sum _ {n = 0} ^ {\ infty} {\ rm {fusc}} (n) x ^ {n}}$

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

Dacă dezvoltăm această funcție, arătăm că fusc ( n +1) este egal cu numărul de modalități de a descompune n ca o sumă de puteri de 2 în următoarea formă, generalizând notația în sistem binar :

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

unde sunt 0, 1 sau 2.

e_i

De exemplu, pentru n = 18, fusc (19) = 7 și 18 are 7 descompuneri, și anume:

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

Enumerare

Secvența lui Stern este implicată în mai multe probleme de numărare.

fusc ( n ) este numărul de subsecvențe de forma 1010 ... 101 (cu o alternanță de 1 și 0, începând și terminând cu 1, posibil limitat la un singur 1) extras din secvența care constituie descompunerea lui n în bază 2. De exemplu în binar, și există fusc (19) = 7 sub-secvențe posibile, și anume 4 secvențe de forma 101 și 3 secvențe limitate la 1. ${\ displaystyle 19 = 10011_ {b}}$

fusc ( n ) este numărul de valori impare k pentru care numărul Stirling de al doilea fel este în sine impar. De exemplu, numerele Stirling care verifică această proprietate pentru n = 9 sunt 1, 3025, 6951, 1 și fusc (9) = 4. ${\ displaystyle \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}}$

Secvență severă și numere raționale

Secvența Stern face posibilă stabilirea unei bijecții între numere întregi pozitive sau zero și numere raționale pozitive sau zero prin intermediul aplicației:

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

Primele imagini ale acestei funcții sunt:

{\ 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}

Fusc număr ( n ) / fusc ( n + 1) este într - adevăr n -lea număr rațional al căii în lățime a copacului caia-Wilf , care stabilește o astfel de bijectie.

Secvența Stern apare și în numeratorii și numitorii fracțiilor construite prin intermediul arborelui Stern-Brocot și care stabilește și o bijecție între numere întregi pozitive sau zero și raționale pozitive sau zero.

Secvența lui Stern și funcția lui Minkowski? ()

Luați în considerare următoarea funcție f , definită peste numere diadice :

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

Această funcție se extinde peste [0,1] într-o funcție continuă strict crescătoare, unu-la-unu de la [0,1] peste [0,1], numită funcția casetă Conway. Reciprocitatea acestei extensii este funcția semnului întrebării al lui Minkowski.

Vezi și tu

Bibliografie

Continuarea lui Stern-Brocot, sora lui Fibonacci , în Pour la Science , nr. 420, octombrie 2012
Sam Northshield, secvența diatomică a lui Stern , American Math. Lunar, 117 , (august-septembrie 2010), 581-598

Articole similare

Referințe

MA Stern, Über einse zahlentheoretische Function , J. Reine Agnew. Matematica. , 55 , (1858), 193-220
(în) EW Dijkstra, „ Un exercițiu pentru Dr.RMBurstall ” ,1976
(în) EW Dijkstra, „ Mai multe despre funcția„ DREF ”(O continuare a EWD570) ” ,1976
Valerio De Angelis, „ Secvența diatomică severă prin polinoamele Chebyshev generalizate ”, Amer. Matematica. lunar , vol. 124, nr . 5,Mai 2017, p. 451-455. Dovada constă în verificarea faptului că determinantul și secvența Stern îndeplinesc relații identice de recurență.
Richard P. Stanley, „ Unele recurențe liniare motivate de matricea diatomică a lui Stern ” , Amer. Matematica. Lunar , vol. 127, n o 2februarie 2020, p. 100
SR Finch, Constantele matematice , Enciclopedia matematicii și a aplicațiilor sale, vol. 94 Cambridge University Press, (2003)
L. Carlitz, O problemă în partițiile legate de numerele Stirling, Bull. Amar. Matematica. Soc. , 70 , (1964), 275-278
Neil Calkin, Herbert S. Wilf, „ Relating the Rationals ” , Amer. Matematica. Lunar ,aprilie 2000, p. 360-363