login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007777 Number of overlap-free binary words of length n. 8
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 (list; graph; refs; listen; history; text; internal format)
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
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, 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
Sequence in context: A260732 A062425 A121386 * A082379 A167379 A213476
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)