Asymptotic formula for balanced words
A word \(w\) over the alphabet \(\{0, 1\}\) is said to be balanced, if, for every pair of subwords \(u\) and \(v\) of \(w\) with equal length, one has \(||u|_1-|v|_1| \leq 1\), where \(|w'|_1\) denotes the number of \(1\)s in the word \(w'\). It is well known that for any balanced word \(x = x_1 \dotsm x_n\) one can find a slope \(\alpha \in [0,1]\) and intercept \(\rho \in [0,1)\) such that \[ x_j = \lfloor \alpha(j+1)+\rho \rfloor - \lfloor \alpha j+\rho \rfloor \] for every \(j = 1, \dotsc, n\). Naturally the choice of \(\alpha, \rho\) is not unique. Rather a balanced word corresponds to \(\rho, \alpha\) in a convex polygon in \([0, 1) \times [0,1]\). This is nicely demonstrated in Figure 1 of the manuscript. Write \(B(n, t, u)\) for the cardinality of the set of balanced words of length \(n\) with \(\alpha \in [1-t, 1]\) and \(\rho \in [0, u)\). In Theorem 1, the author shows that \[ B(n, t, u) = 1+ \sum_{m \leq n} \sum_{0 \leq i < j \leq m, \, (i, j) = 1 \\ i/j \leq t, \, \langle mi/j \rangle < u} 1, \] where \(\langle x \rangle = x - \lfloor x \rfloor\). Then the author goes on to employ techniques from analytic number theory to provide asymptotic formulae for \(B(n, t, u)\). In particular in Theorem 2 it is shown that \[ B(n, t, u) = \frac{tu}{\pi^2} n^3 + O(n^2(\log n)^{15/2}). \]
- A GEOMETRIC PROOF OF THE ENUMERATION FORMULA FOR STURMIAN WORDS
- A new geometric approach to Sturmian words
- A zero-density theorem for the Riemann zeta-function
- Farey series and the Riemann hypothesis
- Fluctuations in the mean of Euler's phi function
- scientific article; zbMATH DE number 3885787 (Why is no real title available?)
- scientific article; zbMATH DE number 1737190 (Why is no real title available?)
- scientific article; zbMATH DE number 3995796 (Why is no real title available?)
- scientific article; zbMATH DE number 2121181 (Why is no real title available?)
- scientific article; zbMATH DE number 3235403 (Why is no real title available?)
- scientific article; zbMATH DE number 3255845 (Why is no real title available?)
- Multiplicative number theory. I. Classical theory
- On the arithmetical complexity of Sturmian words
- On the Changes of Sign of a Certain Error Function
- On the Farey series and the Hecke L-functions
- On the Farey series and the Riemann hypothesis
- Oscillations of the remainder term related to the Euler totient function
- Some combinatorial properties of Sturmian words
- Statistical problems related to irrational rotations
- The continued fraction expansion of α with μ(α) = 3
- The distribution of Farey points
- Balances of m-bonacci Words
- The most unbalanced words \(0^{q-p}1^{p}\) and majorization
- Balanced words and majorization
- On the Number of Balanced Words of Given Length and Height over a Two-Letter Alphabet
- Some results on digital segments and balanced words
- Triangular partitions: enumeration, structure, and generation
- On factorially balanced sets of words
This page was built for publication: Asymptotic formula for balanced words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2116747)
