A007777 Number of overlap-free binary words of length n.

1, 2, 4, 6, 10, 14, 20, 24, 30, 36, 44, 48, 60, 60, 62, 72, 82, 88, 96, 112, 120, 120, 136, 148, 164, 152, 154, 148, 162, 176, 190, 196, 210, 216, 224, 228, 248, 272, 284, 296, 300, 296, 320, 332, 356, 356, 376, 400, 416, 380, 382, 376, 382, 356, 374, 392, 410

Offset: 0

Author

Julien Cassaigne (cassaign(AT)clipper.ens.fr)

Keywords

• nonn
• easy
• nice

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.

Crossrefs

Cf. A028445, A038952, A082379, A082380.

Programs

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 *)

Extensions

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 09 2005