Sterns diatomiske suite

I matematik , Sterns diatomisk sekvens er en sekvens af naturlige tal indført ved matematikeren Moritz Stern i 1858, og hvis første udtryk er:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4,… (fortsættelse A002487 af OEIS ).

Den n -værdi af denne sekvens er fusc ( n ), hvor funktionen fusc er defineret af følgende gentagelsesrelationer :

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

Navnet "fusc" blev givet uden forklaring af Edsger W. Dijkstra i 1976.

Vi kan oprette sekvensen linje for linje ved at fortsætte i henhold til figuren overfor. Hvis vi udelader det første punkt 0, starter vi fra linje 1 - 1. Så kopieres hver nye linje fra den foregående linje ved at indsætte tal, hvor hvert nye nummer er summen af de to tal, der er placeret på hver side af sin position i den forrige linje.

Ejendomme

Hvis vi har Stern-sekvensen i på hinanden følgende linier på 1, 2, 4, 8, ... termer, som i figuren modsat, vises nogle bemærkelsesværdige egenskaber.

Summen af termerne i hver række er en styrke på 3.
Maksimum for hver linje udgør Fibonacci-sekvensen .
Hvis vi udelader den første 1, er hver række et palindrom .

Hver kolonne danner en aritmetisk sekvens . Sekvensen dannet af årsager er selve Sternens sekvens. Dette betyder, at Sterns suite har en fraktal struktur .

Hvis vi nedbryder heltalet n til binært : hvis kræfterne falder, er fusc ( n ) lig med determinanten for den trediekantede matrix : ${\ 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 & \ prikker & 0 \\ 1 & d_ {r-1} -d_ {r-2} + 1 & 1 & 0 & \ prikker & 0 \\\ vdots &&& \ prikker && \ vdots \\ 0 & \ prikker & 0 & 1 & d_ {2} -d_ {1} + 1 & 1 \\ 0 & \ prikker & 0 & 0 & 1 & d_ {1} -d_ {0} +1 \\\ slut {pmatrix}}}$

For eksempel er matrixen med determinant fusc (13) = 5. Denne egenskab gør det muligt at vise, at det heltal m opnået fra n ved at vende rækkefølgen af dets binære cifre har det samme billede som n ved fusc. Således for n = 13 = 0b1101 har vi m = 0b1011 = 11 og fusc (11) = 5. ${\ displaystyle n = 13 = 2 ^ {3} + 2 ^ {2} + 2 ^ {0}}$ ${\ displaystyle {\ begin {pmatrix} 2 & 1 \\ 1 & 3 \ end {pmatrix}}}$

Fraktal struktur

Sekvensens fraktale struktur vises også i forbindelse med Sierpiński-trekanten . Sidstnævnte kan udfyldes trin for trin fra Pascals trekant ved at gøre de ulige tal mørkere og gøre de lige tal hvidere. Hvis vi tæller de ulige tal langs de stigende diagonaler i Pascals trekant, får vi Stern-sekvensen. I den modsatte figur er de ulige numre blevet erstattet af 1s og de lige tal med 0s. Denne proces kan sammenlignes med at opnå vilkårene for Fibonacci-sekvensen ved at summere vilkårene for de stigende diagonaler i Pascals trekant.

Vi kan endelig visualisere dette aspekt ved grafisk at repræsentere punkterne ( n , fusc ( n )) i sekvensen.

Generatorserie

Den genererende serie af Stern-sekvensen er lig med: ${\ 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}} \ højre )}

Hvis vi udvikler denne funktion, viser vi, at fusc ( n +1) er lig med antallet af måder at nedbryde n som en sum af kræfter på 2 i følgende form, hvilket genererer notationen i binært system :

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

hvor de er 0, 1 eller 2.

e_i

For eksempel, for n = 18, har fusc (19) = 7 og 18 7 nedbrydninger, nemlig:

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

Optælling

Sterns sekvens er involveret i flere tælleproblemer.

fusc ( n ) er antallet af sekvenser af formen 1010 ... 101 (med en alternering på 1 og 0, der starter og slutter med 1, muligvis begrænset til en enkelt 1) ekstraheret fra sekvensen, der udgør nedbrydningen af n i base 2. For eksempel i binær, og der er fusc (19) = 7 mulige undersekvenser, nemlig 4 sekvenser af form 101 og 3 sekvenser begrænset til 1. ${\ displaystyle 19 = 10011_ {b}}$

fusc ( n ) er antallet af ulige værdier k, hvor Stirling-nummeret af den anden slags i sig selv er ulige. For eksempel er Stirling-numrene, der bekræfter denne egenskab for n = 9, 1, 3025, 6951, 1 og fusc (9) = 4. ${\ displaystyle \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ højre \}}$

Akter rækkefølge og rationelle tal

Stern-sekvensen gør det muligt at etablere en sammenhæng mellem positive eller nul heltal og positive eller nul rationelle tal ved hjælp af applikationen:

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

De første billeder af denne funktion er:

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

Antallet fusc ( n ) / fusc ( n + 1) er faktisk n th rationelt tal af stien i bredden af Calkin-Wilf træ , der fastlægger en sådan bijection.

Stern-sekvensen vises også i tællere og nævnere af fraktioner konstrueret ved hjælp af Stern-Brocot-træet , og som også etablerer en sammenhæng mellem positive eller nul heltal og positive eller nul rationelle.

Sterns sekvens og Minkowskis funktion? ()

Overvej følgende funktion f , defineret over dyadiske tal :

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

Denne funktion strækker sig over [0,1] til en strengt stigende kontinuerlig funktion, en-til-en fra [0,1] over [0,1], kaldet Conway box-funktionen. Det gensidige ved denne udvidelse er Minkowskis spørgsmålstegnfunktion .

Se også

Bibliografi

Fortsættelsen af Stern-Brocot, søster til Fibonacci , i Pour la Science , nr. 420, oktober 2012
Sam Northshield, Sterns diatomiske sekvens , amerikansk matematik. Månedligt, 117 , (august-september 2010), 581-598

Relaterede artikler

Referencer

MA Stern, Über einse zahlentheoretische Function , J. Reine Agnew. Matematik. , 55 , (1858), 193-220
(i) EW Dijkstra, " En øvelse for Dr.RMBurstall " ,1976
(in) EW Dijkstra, " Mere om funktionen" DREF "(En efterfølger til EWD570) " ,1976
Valerio De Angelis, “ Stern Diatomic Sequence via the Generalised Chebyshev Polynomials ”, Amer. Matematik. månedligt , vol. 124, nr . 5,Maj 2017, s. 451-455. Beviset består i at verificere, at determinanten og Stern-sekvensen opfylder identiske gentagelsesforhold.
Richard P. Stanley, ” Nogle lineære gentagelser motiveret af Sterns Diatomic Array, ” Amer. Matematik. Månedligt , vol. 127, nr . 2februar 2020, s. 100
SR Finch, matematiske konstanter , encyklopædi for matematik og dens anvendelser, bind 94 Cambridge University Press, (2003)
L. CARLITZ, Et problem i skillevægge relateret til Stirling numre, Bull. Bitter. Matematik. Soc. , 70 , (1964), 275-278
Neil Calkin, Herbert S. Wilf, " Recounting the Rationals " , Amer. Matematik. Månedligt ,april 2000, s. 360-363