OFFSET
0,2
REFERENCES
J. Cassaigne, Counting overlap-free binary words, pp. 216-225 of STACS '93, Lect. Notes Comput. Sci., Springer-Verlag, 1993.
J. Cassaigne, Motifs évitables et régularités dans les mots (Thèse de Doctorat), Tech. Rep. LITP-TH 94-04, Institut Blaise Pascal, Paris, 1994.
Raphael M. Jungers, Vladimir Yu. Protasov and Vincent D. Blondel, Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices, in LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science, Volume 4957/2008, [From N. J. A. Sloane, Jul 10 2009]
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Franz-Josef Brandenburg, Uniformly Growing k-th Power-Free Homomorphisms, Theoretical Computer Science, volume 23, 1983, pages 69-82. See density of two letter weakly square-free strings (as overlap-free is called in this paper) after theorem 12 page 80. A misprint omits a(14) = 62 from the list of values.
J. Cassaigne, Counting overlap-free binary words, Preprint. (Annotated scanned copy)
J. Cassaigne, Counting overlap-free binary words
J. Cassaigne, Motifs évitables et régularités dans les mots, Thèse de Doctorat, Paris, 1994.
K. Jarhumaki and J. Shallit, Polynomial vs Exponential Growth in Repetition-Free Binary Words, arXiv:math/0304095 [math.CO], 2003.
Eric Weisstein's World of Mathematics, Overlapfree Word.
MAPLE
delta:=linalg[matrix](4, 4, [0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0]); iota:=linalg[matrix](4, 4, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]); kappa:=linalg[matrix](4, 4, [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
V:=proc(n) options remember: if n>7 and n mod 2 =1 then RETURN(evalm(kappa &* V((n+1)/2) &* transpose(delta) + delta &* V((n+1)/2) &* transpose(kappa))) elif n=5 then RETURN(linalg[matrix](4, 4, [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])) elif n=7 then RETURN(linalg[matrix](4, 4, [0, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0])) else RETURN(linalg[matrix](4, 4, 0)) fi: end;
U:=proc(n) options remember: if n>7 and n mod 2 =1 then RETURN(evalm(iota &* V((n+1)/2) &* transpose(delta) + delta &* V((n+1)/2) &* transpose(iota) + (kappa+iota) &* U((n+1)/2) &* transpose(delta) + delta &* U((n+1)/2) &* transpose(kappa+iota))) elif n>7 and n mod 2 =0 then RETURN(evalm(iota &* V(n/2) &* transpose(iota) + delta &* V(n/2+1) &* transpose(delta) + (kappa+iota) &* U(n/2) &* transpose(kappa+iota) + delta &* U(n/2+1) &* transpose(delta))) elif n=4 then RETURN(linalg[matrix](4, 4, [2, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 2])) elif n=5 then RETURN(linalg[matrix](4, 4, [0, 2, 2, 0, 2, 0, 0, 2, 2, 0, 2, 0, 0, 2, 0, 0])) elif n=6 then RETURN(linalg[matrix](4, 4, [2, 2, 0, 2, 2, 2, 2, 0, 0, 2, 2, 0, 2, 0, 0, 2])) elif n=7 then RETURN(linalg[matrix](4, 4, [4, 2, 0, 2, 2, 0, 2, 2, 0, 2, 0, 2, 2, 2, 2, 0])) fi: end;
a:=proc(n) if n<4 then RETURN([1, 2, 4, 6][n+1]) else RETURN(add(add(U(n)[i, j], i=1..4), j=1..4)) fi: end; seq(a(n), n=0..100); # Pab Ter (pabrlos2(AT)yahoo.com), Nov 09 2005
MATHEMATICA
delta = {{0, 0, 1, 1}, {0, 0, 0, 0}, {0, 1, 0, 0}, {1, 0, 0, 0}};
iota = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};
kappa = {{0, 0, 1, 1}, {1, 1, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};
V[n_] := V[n] = Which[n > 7 && Mod[n, 2] == 1, delta . V[(n+1)/2] . Transpose[kappa] + kappa . V[(n+1)/2] . Transpose[delta], n == 5, {{2, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}, n == 7, {{0, 0, 2, 0}, {0, 2, 0, 0}, {2, 0, 0, 0}, {0, 0, 0, 0}}, True, Array[0& , {4, 4}]];
U[n_] := U[n] = Which[n > 7 && Mod[n, 2] == 1, delta . U[(n+1)/2] . Transpose[iota + kappa] + delta . V[(n+1)/2] . Transpose[iota] + iota . V[(n+1)/2] . Transpose[delta] + (iota + kappa) . U[(n+1)/2] . Transpose[delta], n > 7 && Mod[n, 2] == 0, delta.U[n/2+1] . Transpose[delta] + delta . V[n/2+1] . Transpose[delta] + iota . V[n/2] . Transpose[iota] + (iota + kappa) . U[n/2] . Transpose[iota + kappa], n == 4, {{2, 0, 2, 0}, {0, 2, 0, 0}, {2, 0, 0, 0}, {0, 0, 0, 2}}, n == 5, {{0, 2, 2, 0}, {2, 0, 0, 2}, {2, 0, 2, 0}, {0, 2, 0, 0}}, n == 6, {{2, 2, 0, 2}, {2, 2, 2, 0}, {0, 2, 2, 0}, {2, 0, 0, 2}}, n == 7, {{4, 2, 0, 2}, {2, 0, 2, 2}, {0, 2, 0, 2}, {2, 2, 2, 0}}];
a[n_] := If[n < 4, {1, 2, 4, 6}[[n+1]], Sum[U[n][[i, j]], {i, 1, 4}, {j, 1, 4}]];
Table[a[n], {n, 0, 56}] (* Jean-François Alcover, Jan 02 2013, translated from Pab Ter's Maple program *)
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
Julien Cassaigne (cassaign(AT)clipper.ens.fr)
EXTENSIONS
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 09 2005
STATUS
approved