Finding binary words with a given number of subsequences

DOI10.1016/J.TCS.2022.03.032MaRDI QIDQ6412587arXivFDO

Authors Radosław Żak

Publication date 1 October 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2022.03.032

Mathematics Subject Classification ID

Combinatorics on words (68R15)

arXiv classification

math.CO

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(lognloglogn)$ with exactly $n$ subsequences; this can be improved to $O(logn)$ under assumption of Zaremba's conjecture.

This page was built for publication: Finding binary words with a given number of subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6412587)