The Discrepancy of the Lex-Least De Bruijn Sequence

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We answer the following question of R. L. Graham: What is the discrepancy of the lexicographically-least binary de Bruijn sequence? Here, "discrepancy" refers to the maximum (absolute) difference between the number of ones and the number of zeros in any initial segment of the sequence. We show that the answer is $Θ(2^n \log n/n)$.
11 pages, 0 figures

Keywords

Combinatorics, 05A16 (Primary) 05D40, 68R15 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/224302

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0903.3753
 http://arxiv.org/abs/0903.3753

Collections

arXiv