Sterns diatomiske suite

I matematikk er Sterns diatomiske rekkefølge en sekvens av naturlige tall introdusert av matematikeren Moritz Stern i 1858, og hvis første ord er:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... (fortsettelse A002487 av OEIS ).

Den n- te verdi av denne sekvens er fusc ( n ), der funksjonen fusc er definert av de følgende rekursjonslikninger :

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

Navnet "fusc" ble gitt, uten forklaring, av Edsger W. Dijkstra i 1976.

Vi kan bygge sekvensen linje for linje ved å fortsette i henhold til figuren motsatt. Når vi utelater den første termen 0, starter vi fra linje 1 - 1. Deretter kopieres hver nye linje fra forrige linje ved å sette inn tall, hvor hvert nye nummer er summen av de to tallene som ligger på hver side av posisjonen i forrige linje.

Eiendommer

Hvis vi har Stern-sekvensen i påfølgende linjer med 1, 2, 4, 8, ... termer, som i figuren motsatt, vises noen bemerkelsesverdige egenskaper.

Summen av vilkårene i hver rad er en styrke på 3.
Maksimumene for hver linje utgjør Fibonacci-sekvensen .
Hvis vi utelater første 1, er hver rad et palindrom .

Hver kolonne danner en aritmetisk sekvens . Sekvensen dannet av årsaker er sekvensen til Stern selv. Dette betyr at Sterns suite har en fraktal struktur .

Hvis vi dekomponerer heltallet n i binært :, hvor kraftene blir redusert, er fusc ( n ) lik determinanten til den trekantede matrisen : ${\ 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 & \ 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 \\\ slutt {pmatrix}}}$

For eksempel er matrisen med determinant fusc (13) = 5. Denne egenskapen gjør det mulig å vise at heltallet m oppnådd fra n ved å invertere rekkefølgen på de binære sifrene, har samme bilde som n ved fusc. For n = 13 = 0b1101 har vi altså 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}}}$

Fraktalstruktur

Fraktalstrukturen til sekvensen vises også i forbindelse med Sierpiński-trekanten . Sistnevnte kan fylles ut trinn for trinn fra Pascals trekant ved å mørke oddetallene og bleke partallene. Hvis vi teller oddetallene langs de stigende diagonalene i Pascals trekant, får vi Stern-sekvensen. I figuren motsatt er oddetallene erstattet av 1s og partallene med 0s. Denne prosessen er sammenlignbar med å oppnå vilkårene for Fibonacci-sekvensen ved å summere vilkårene for de stigende diagonalene i Pascals trekant.

Vi kan endelig visualisere dette aspektet ved å grafisk representere punktene ( n , fusc ( n )) i sekvensen.

Generatorserie

Den genererende serien til Stern-sekvensen er lik: ${\ 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 )}

Hvis vi utvikler denne funksjonen, viser vi at fusc ( n +1) er lik antall måter å nedbryte n som en sum av krefter på 2 i følgende form, og generaliserer notasjonen i binært system :

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

der de er 0, 1 eller 2.

e_i

For eksempel, for n = 18, har fusc (19) = 7, og 18 7 nedbrytninger, 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

Oppregning

Starns sekvens er involvert i flere telleproblemer.

fusc ( n ) er antall sekvenser av skjemaet 1010 ... 101 (med en alternasjon på 1 og 0, startende og slutter med 1, muligens begrenset til en enkelt 1) ekstrahert fra sekvensen som utgjør nedbrytningen av n i basen 2. For eksempel i binær, og det er fusc (19) = 7 mulige undersekvenser, nemlig 4 sekvenser av form 101 og 3 sekvenser begrenset til 1. ${\ displaystyle 19 = 10011_ {b}}$

fusc ( n ) er antallet oddverdier k som Stirling-nummeret av den andre typen i seg selv er merkelig for. For eksempel er Stirling-tallene som bekrefter denne egenskapen for n = 9 1, 3025, 6951, 1 og fusc (9) = 4. ${\ displaystyle \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}}$

Akterrekke og rasjonelle tall

Stern-sekvensen gjør det mulig å etablere en sammenheng mellom positive eller null heltall og positive eller null rasjonelle tall ved hjelp av applikasjonen:

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

De første bildene av denne funksjonen 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}

Tallet fusc ( n ) / fusc ( n + 1) er faktisk den n -te rasjonell antall av banen i bredde av den Calkin-Wilf treet , som etablerer en slik Bijeksjon.

Stern-sekvensen vises også i tellerne og nevnerne for brøk konstruert ved hjelp av Stern-Brocot-treet , og som også etablerer en sammenheng mellom positive eller null heltall og positive eller null rasjonelle.

Sterns sekvens og Minkowskis funksjon? ()

Tenk på følgende funksjon f , definert over dyadiske tall :

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

Denne funksjonen strekker seg over [0,1] til en streng økende kontinuerlig funksjon, en-til-en fra [0,1] over [0,1], kalt Conway-boksfunksjonen. Det gjensidige av denne utvidelsen er Minkowskis spørsmålstegnfunksjon .

Se også

Bibliografi

Fortsettelsen av Stern-Brocot, søster til Fibonacci , i Pour la Science , nr. 420, oktober 2012
Sam Northshield, Sterns diatomiske sekvens , amerikansk matematikk. Månedlig, 117 , (august-september 2010), 581-598

Relaterte artikler

Referanser

MA Stern, Über einse zahlentheoretische Function , J. Reine Agnew. Matte. , 55 , (1858), 193-220
(i) EW Dijkstra, " En øvelse for Dr.RMBurstall " ,1976
(in) EW Dijkstra, " Mer om funksjonen" DREF "(En oppfølger til EWD570) " ,1976
Valerio De Angelis, “ The Stern Diatomic Sequence via the Generalized Chebyshev Polynomials ”, Amer. Matte. månedlig , vol. 124, n o 5,Mai 2017, s. 451-455. Beviset består i å verifisere at determinanten og Stern-sekvensen tilfredsstiller identiske gjentakelsesforhold.
Richard P. Stanley, “ Noen lineære gjentakelser motivert av Sterns Diatomic Array, ” Amer. Matte. Månedlig , vol. 127, n o tofebruar 2020, s. 100
SR Finch, Mathematical konstants , Encyclopedia of mathematics and its applications, vol. 94 Cambridge University Press, (2003)
L. Carlitz, Et problem i skillevegger relatert til Stirling tall, Bull. Bitter. Matte. Soc. , 70 , (1964), 275-278
Neil Calkin, Herbert S. Wilf, “ Recounting the Rationals ” , Amer. Matte. Månedlig ,april 2000, s. 360-363