Sternova diatomická souprava

V matematiky , diatomic sekvence Sterna je sekvence z přirozených čísel zavedených matematik Moritz Stern v roce 1858, a jehož první termíny jsou:

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... (pokračování A002487 na OEIS ).

N- tá hodnota z této sekvence je fusc ( n ), kde je funkce fusc definován následujícími Rekurentní vztahy :

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

Název „fusc“ dal bez vysvětlení Edsger W. Dijkstra v roce 1976.

Můžeme sestavit sekvenci řádek po řádku podle postupu na opačném obrázku. Vynecháme-li první člen 0, začneme od řádku 1 - 1. Poté se každý nový řádek zkopíruje z předchozího řádku vložením čísel, přičemž každé nové číslo je součtem dvou čísel umístěných na obou stranách jeho polohy v předchozím řádku.

Vlastnosti

Pokud máme Sternovu sekvenci v po sobě jdoucích řádcích 1, 2, 4, 8, ... podmínek, jako na obrázku opačně, objeví se některé pozoruhodné vlastnosti.

Součet podmínek v každém řádku je mocninou 3.
Maximum každého řádku tvoří Fibonacciho sekvenci .
Pokud vynecháme počáteční 1, každý řádek je palindrom .

Každý sloupec tvoří aritmetickou sekvenci . Posloupnost tvořená důvody je posloupností samotného Sterna. To znamená, že Sternovo apartmá má fraktální strukturu .

Rozložíme -li celé číslo n na binární :, přičemž síly se zmenšují, pak fusc ( n ) se rovná determinantu tridiagonální matice : ${\ displaystyle n = 2 ^ {d_ {r}} + 2 ^ {d_ {r-1}} + \ tečky + 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 & \ tečky & 0 & 0 & 1 & d_ {1} -d_ {0} +1 \\\ konec {pmatrix}}}$

Například pro matici je s determinantem fusc (13) = 5. Tato vlastnost umožňuje ukázat, že celé číslo m získané z n převrácením pořadí jeho binárních číslic má stejný obraz jako n pomocí fusc. Takže pro n = 13 = 0b1101 máme m = 0b1011 = 11 a fusc (11) = 5. ${\ displaystyle n = 13 = 2 ^ {3} + 2 ^ {2} + 2 ^ {0}}$ ${\ displaystyle {\ begin {pmatrix} 2 & 1 \\ 1 & 3 \ end {pmatrix}}}$

Fraktální struktura

Fraktální struktura sekvence se také objevuje v souvislosti s Sierpińského trojúhelníkem . Ten může být vyplněn krok za krokem z Pascalova trojúhelníku ztmavením lichých čísel a vybělením sudých čísel. Pokud spočítáme lichá čísla podél vzestupných úhlopříček Pascalova trojúhelníku, dostaneme Sternovu sekvenci. Na opačném obrázku byla lichá čísla nahrazena 1 s a sudá čísla 0 s. Tento proces je srovnatelný se získáním podmínek Fibonacciho posloupnosti sečtením podmínek vzestupných úhlopříček Pascalova trojúhelníku.

Nakonec můžeme tento aspekt vizualizovat grafickým znázorněním bodů ( n , fusc ( n )) sekvence.

Řada generátorů

Série generující z Stern sekvence se rovná: ${\ displaystyle G (x) = \ součet _ {n = 0} ^ {\ infty} {\ rm {fusc}} (n) x ^ {n}}$

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

Pokud vyvineme tuto funkci, ukážeme, že fusc ( n +1) se rovná počtu způsobů, jak rozložit n jako součet mocnin 2 v následující podobě, zobecňující notaci v binární soustavě :

{\ displaystyle n = e_ {0} + 2e_ {1} + 4e_ {2} + 8e_ {3} + \ tečky}

kde jsou 0, 1 nebo 2.

e_i

Například pro n = 18 má fusc (19) = 7 a 18 7 rozkladů, jmenovitě:

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

Výčet

Sternova sekvence je zapojena do několika problémů s počítáním.

fusc ( n ) je počet subsekvencí formuláře 1010 ... 101 (se střídáním 1 a 0, počínaje a končením 1, případně omezený na jednu 1) extrahovaný ze sekvence tvořící rozklad n v bázi 2. Například v binární podobě a existuje fusc (19) = 7 možných dílčích sekvencí, konkrétně 4 sekvence ve formě 101 a 3 sekvence omezené na 1. ${\ displaystyle 19 = 10011_ {b}}$

fusc ( n ) je počet lichých hodnot k, pro které je samotné Stirlingovo číslo druhého druhu liché. Například Stirlingova čísla ověřující tuto vlastnost pro n = 9 jsou 1, 3025, 6951, 1 a fusc (9) = 4. ${\ displaystyle \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}}$

Přísná posloupnost a racionální čísla

Sternova sekvence umožňuje stanovit bijekci mezi kladnými nebo nulovými celými čísly a kladnými nebo nulovými racionálními čísly pomocí aplikace:

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

První obrázky této funkce jsou:

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

Číslo fusc ( n ) / fusc ( n + 1) je skutečně n -tý racionální číslo od cesty v šířce části stromu Calkin-Wilf , který stanoví takový bijection.

Sternova posloupnost se také objevuje v čitatelích a jmenovatelech zlomků vytvořených pomocí Stern-Brocotova stromu , a která také stanoví bijekci mezi kladnými nebo nulovými celými čísly a kladnými nebo nulovými racionály.

Sternova posloupnost a Minkowského funkce? ()

Zvažte následující funkci f , definovanou přes dyadická čísla :

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

Tato funkce přesahuje [0,1] do přísně rostoucí spojité funkce, jedna ku jedné od [0,1] přes [0,1], nazývaná Conwayova funkce. Převrácená hodnota tohoto rozšíření je funkce Minkowského otazníku .

Podívejte se také

Bibliografie

Pokračování Stern-Brocotové, sestry Fibonacci , v Pour la Science , č. 420, říjen 2012
Sam Northshield, Sternova diatomická sekvence , American Math. Měsíčně, 117 , (srpen-září 2010), 581-598

Související články

Reference

MA Stern, Über einse zahlentheoretische Function , J. Reine Agnew. Matematika. , 55 , (1858), 193-220
(in) EW Dijkstra, „ Cvičení pro Dr.RMBurstall “ ,1976
(in) EW Dijkstra, „ Více o funkci„ DREF “(pokračování EWD570) “ ,1976
Valerio De Angelis, „ The Stern Diatomic Sequence via the Generalized Chebyshev Polynomials “, Amer. Matematika. měsíčně , sv. 124, n o 5,Květen 2017, str. 451-455. Důkaz spočívá v ověření, že determinant a Sternova sekvence splňují stejné relace opakování.
Richard P. Stanley, „ Některé lineární rekurence motivované Sternovým diatomickým polem, “ Amer. Matematika. Měsíčně , sv. 127, n O 2února 2020, str. 100
SR Finch, Matematické konstanty , Encyklopedie matematiky a její aplikace, sv. 94 Cambridge University Press, (2003)
L. Carlitz, Problém v oddílech souvisejících se Stirlingovými čísly, Bull. Hořký. Matematika. Soc. , 70 , (1964), 275-278
Neil Calkin, Herbert S. Wilf, „ Recording the Rationals “ , Amer. Matematika. měsíčně ,dubna 2000, str. 360-363