Finding binary words with a given number of subsequences

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.

References in corpus (2)

• The Number of Distinct Subsequences of a Random Binary String
• Expected Number of Distinct Subsequences in Randomly Generated Binary Strings