On the maximum number of distinct factors of a binary string
If \(x,y\), and \(z\) denote three strings of 0's and 1's, then \(y\) is called a factor of the string \(xyz\) (obtained by concatenation). The number of distinct factors of a string \(w\) is denoted by \(d(w)\). So \(d(10110)=12\). Two theorems are proved. The first is the (easy) result: Theorem. If \(| w|=n\), then \(d(w)\leq{n-k+1\choose 2}+2^{k+1}-1\), where \(k\) is the unique integer such that \(2^ k+k-1\leq n<2^{k+1}+k\). The main result is the fact that equality is attained for all \(n\). The proof depends on a lemma stating that, for \(2^ k\leq i\leq 2^{k+1}\), the De Bruijn graph \(B_ k\) (on \(2^ k\) vertices) contains a closed path of length \(i\) (a misprint in the paper states \(k)\) that visits every vertex at least once. The proof of the lemma is based on a result of \textit{M. Yoeli} [Binary ring sequences, Am. Math. Mon. 69, 852-855 (1962; Zbl 0107.249)] which states that \(B_ k\) contains a cycle of length \(i\) for any \(i\) such that \(0<i\leq 2^ k\) and also a closed path of length \(i+2^ k\).
- Total palindrome complexity of finite words
- On the combinatorics of finite words
- Complexity for finite factors of infinite sequences
- The theorem of the k-1 happy divorces
- On semi-perfect de Bruijn words
- Uniform words
- String factorisations with maximum or minimum dimension
- Maximal state complexity and generalized de Bruijn words
- Sublinear algorithms for approximating string compressibility
- Subsequence frequency in binary words
- On some 2-binomial coefficients of binary words: geometrical interpretation, partitions of integers, and fair words
- On average sequence complexity
This page was built for publication: On the maximum number of distinct factors of a binary string
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366959)
