6533b862fe1ef96bd12c775a

RESEARCH PRODUCT

Asymptotic bit frequency in Fibonacci words

Jean-luc BarilSergey KirgizovVincent Vajnovszki

subject

[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]FOS: Computer and information sciences[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Mathematics::CombinatoricsDiscrete Mathematics (cs.DM)[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]FOS: MathematicsMathematics - CombinatoricsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Combinatorics (math.CO)[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematics

description

It is known that binary words containing no $k$ consecutive 1s are enumerated by $k$-step Fibonacci numbers. In this note we discuss the expected value of a random bit in a random word of length $n$ having this property.

yearjournalcountryeditionlanguage
2021-06-28
https://dx.doi.org/10.48550/arxiv.2106.13550