Polynomial versus Exponential Growth in Repetition-Free Binary Words

Juhani Karhumaki, Jeffrey Shallit

It is known that the number of overlap-free binary words of length n grows polynomially, while the number of cubefree binary words grows exponentially. We show that the dividing li…