login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007777 Number of overlap-free binary words of length n. 6
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

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

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

Cf. A028445, A038952, A082379, A082380.

Sequence in context: A260732 A062425 A121386 * A082379 A167379 A213476

Adjacent sequences:  A007774 A007775 A007776 * A007778 A007779 A007780

KEYWORD

nonn,easy,nice

AUTHOR

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

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 26 14:28 EDT 2021. Contains 348267 sequences. (Running on oeis4.)