How many square occurrences must a binary sequence contain? - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue The Electronic Journal of Combinatorics Année : 2003

How many square occurrences must a binary sequence contain?

Pascal Ochem
Michael Rao

Résumé

Every binary word with at least four letters contains a square. A.~Fraenkel and J.~Simpson \cite{FraenkelSimpson95} showed that three {\em distinct squares} are necessary and sufficient to construct an infinite binary word. We study the following complementary question: how many {\em square occurrences} must a binary word contain? We show that this quantity is, in the limit, a constant fraction of the word length, and prove that this constant is $0.55080...$.

Domaines

Autre [cs.OH]

Dates et versions

inria-00099596 , version 1 (26-09-2006)

Identifiants

Citer

Gregory Kucherov, Pascal Ochem, Michael Rao. How many square occurrences must a binary sequence contain?. The Electronic Journal of Combinatorics, 2003, 10 (1), 11 p. ⟨10.37236/1705⟩. ⟨inria-00099596⟩
76 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More