A pattern sequence approach to Stern's sequence

DOI10.1016/J.DISC.2011.07.029MaRDI QIDQ409393zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael Coons, Jeffrey Shallit

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.0086

zbMATH Keywords

pattern sequence expansionStern sequence

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15) Automata sequences (11B85)

Abstract: Let w be a binary string and let a_w (n) be the number of occurrences of the word w in the binary expansion of n. As usual we let s(n) denote the Stern sequence; that is, s(0)=0, s(1)=1, and for n >= 1, s(2n)=s(n) and s(2n+1)=s(n)+s(n+1). In this note, we show that s(n) = a_1 (n) + sum_{w in 1 (0+1)*} s([w bar]) a_{w1} (n) where w bar denotes the complement of w (obtained by sending 0 to 1 and 1 to 0, and [w] denotes the integer specified by the word w interpreted in base 2.

Recommendations

• A correlation identity for Stern's sequence
• Sturmian words and the Stern sequence
• The modular distribution of Stern's sequence
• On some conjectures concerning Stern's sequence and its twist
• Stern's diatomic sequence \(0, 1, 1, 2, 1, 3, 2, 3, 1, 4, \dots \)

Cites work

• scientific article; zbMATH DE number 2018401 (Why is no real title available?)
• Automatic Sequences
• Paper Folding, Digit Patterns and Groups of Arithmetic Fractals
• Pattern spectra, substring enumeration, and automatic sequences
• Stern's diatomic sequence \(0, 1, 1, 2, 1, 3, 2, 3, 1, 4, \dots \)
• The ring of \(k\)-regular sequences

Cited in

(6)

• Asymptotic analysis of \(q\)-recursive sequences
• A correlation identity for Stern's sequence
• Combinatorics on patterns of a bidimensional Sturmian sequence
• Counting the number of non-zero coefficients in rows of generalized Pascal triangles
• Non-standard binary representations and the Stern sequence
• Sturmian words and the Stern sequence

This page was built for publication: A pattern sequence approach to Stern's sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409393)