Back to Search
Start Over
Finding binary words with a given number of subsequences
- Source :
- \.Zak R., Finding binary words with a given number of subsequences, Theoretical Computer Science 919 (2022), pp. 75-79
- Publication Year :
- 2022
-
Abstract
- We relate binary words with a given number of subsequences to continued fractions of rational numbers with a given denominator. We deduce that there are binary strings of length $O(\log n \log \log n)$ with exactly $n$ subsequences; this can be improved to $O(\log n)$ under assumption of Zaremba's conjecture.
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- \.Zak R., Finding binary words with a given number of subsequences, Theoretical Computer Science 919 (2022), pp. 75-79
- Publication Type :
- Report
- Accession number :
- edsarx.2210.00342
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.03.032