The Number of Threshold Words on n Letters Grows Exponentially for Every n ≥ 27
James D. Currie, Lucas Mol, and Narad Rampersad
Department of Mathematics and Statistics
University of Winnipeg
515 Portage Avenue
Winnipeg, MB R3B 2E9
Canada
Abstract:
For every n ≥ 27, we show that the number of
n/(n−1)+-free words (i.e., threshold words) of length
k on n letters grows exponentially in k. This
settles all but finitely many cases of a conjecture of Ochem.
Full version: pdf,
dvi,
ps,
latex
Received November 13 2019; revised version received February 21 2020.
Published in Journal of Integer Sequences,
February 22 2020.
Return to
Journal of Integer Sequences home page
