Counting Subwords Occurrences in Base-b Expansions

Abstract

We count the number of distinct (scattered) subwords occurring in the base-b expansion of the non-negative integers. More precisely, we consider the sequence $(S_b(n){)}_{n\ge 0}$ counting the number of positive entries on each row of a generalization of the Pascal triangle to binomial coefficients of base-$b$ expansions. By using a convenient tree structure, we provide recurrence relations for $(S_b(n){)}_{n\ge 0}$ leading to the $b$-regularity of the latter sequence. Then we deduce the asymptotics of the summatory function of the sequence $(S_b(n){)}_{n\ge 0}$.

22 pages, 9 figures

References in corpus (2)

• Cluster algebras and continued fractions
• Self-Similar Corrections to the Ergodic Theorem for the Pascal-Adic Transformation