Journal of Integer Sequences, Vol. 23 (2020), Article 20.3.1

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


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