

A028445


Number of cubefree words of length n on two letters.


12



1, 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, 174, 254, 378, 554, 802, 1168, 1716, 2502, 3650, 5324, 7754, 11320, 16502, 24054, 35058, 51144, 74540, 108664, 158372, 230800, 336480, 490458, 714856, 1041910, 1518840, 2213868
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 0..47 [copied from Edlin paper]
A. E. Edlin, Cubefree words
Mari Huova, Combinatorics on Words. New Aspects on Avoidability, Defect Effect, Equations and Palindromes, Turku Centre for Computer Science, TUCS Dissertations No 172, April 2014.
K. Jarhumaki and J. Shallit, Polynomial vs Exponential Growth in RepetitionFree Binary Words, arXiv:math/0304095 [math.CO], 2003.
R. Kolpakov, Efficient Lower Bounds on the Number of Repetitionfree Words, J. Integer Sequences, Vol. 10 (2007), Article 07.3.2.
A. M. Shur, Growth properties of powerfree languages, Computer Science Review, Vol. 6 (2012), 187208.
A. M. Shur, Numerical values of the growth rates of powerfree languages, arXiv:1009.4415 [cs.FL], 2010.
Eric Weisstein's World of Mathematics, Cubefree Word.


FORMULA

Let L = lim a(n)^(1/n); then L exists since a(n) is submultiplicative, and 1.4575732 < L < 1.4575772869240 (Shur 2010). Empirical: L=1.4575772869237..., i.e. the upper bound is very precise.  Arseny Shur, Apr 27 2015


MATHEMATICA

Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {___, x__, x__, x__, ___}] &, {{}}, 20] (* Vladimir Reshetnikov, May 16 2016 *)


CROSSREFS

Cf. A007777, A082379, A082380.
Sequence in context: A132002 A098151 A211971 * A006305 A067247 A017985
Adjacent sequences: A028442 A028443 A028444 * A028446 A028447 A028448


KEYWORD

nonn


AUTHOR

Anne Edlin (anne(AT)euclid.math.temple.edu)


EXTENSIONS

a(29)a(36) from Lars Blomberg, Aug 22 2013


STATUS

approved



