login
Number of overlap-free binary words of length n.
8

%I #51 Aug 03 2024 05:43:00

%S 1,2,4,6,10,14,20,24,30,36,44,48,60,60,62,72,82,88,96,112,120,120,136,

%T 148,164,152,154,148,162,176,190,196,210,216,224,228,248,272,284,296,

%U 300,296,320,332,356,356,376,400,416,380,382,376,382,356,374,392,410

%N Number of overlap-free binary words of length n.

%D J. Cassaigne, Counting overlap-free binary words, pp. 216-225 of STACS '93, Lect. Notes Comput. Sci., Springer-Verlag, 1993.

%D 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.

%D 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]

%H Vincenzo Librandi, <a href="/A007777/b007777.txt">Table of n, a(n) for n = 0..1000</a>

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.

%H Franz-Josef Brandenburg, <a href="https://doi.org/10.1016/0304-3975(88)90009-6">Uniformly Growing k-th Power-Free Homomorphisms</a>, 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.

%H J. Cassaigne, <a href="/A007777/a007777.pdf">Counting overlap-free binary words</a>, Preprint. (Annotated scanned copy)

%H J. Cassaigne, <a href="http://iml.univ-mrs.fr/~cassaign/publis/overlap.ps.gz">Counting overlap-free binary words</a>

%H J. Cassaigne, <a href="http://iml.univ-mrs.fr/~cassaign/these/">Motifs évitables et régularités dans les mots</a>, Thèse de Doctorat, Paris, 1994.

%H K. Jarhumaki and J. Shallit, <a href="https://arxiv.org/abs/math/0304095">Polynomial vs Exponential Growth in Repetition-Free Binary Words</a>, arXiv:math/0304095 [math.CO], 2003.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/OverlapfreeWord.html">Overlapfree Word</a>.

%p 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]);

%p 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;

%p 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;

%p 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

%t delta = {{0, 0, 1, 1}, {0, 0, 0, 0}, {0, 1, 0, 0}, {1, 0, 0, 0}};

%t iota = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};

%t kappa = {{0, 0, 1, 1}, {1, 1, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};

%t 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}]];

%t 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}}];

%t a[n_] := If[n < 4, {1, 2, 4, 6}[[n+1]], Sum[U[n][[i, j]], {i, 1, 4}, {j, 1, 4}]];

%t Table[a[n], {n, 0, 56}] (* _Jean-François Alcover_, Jan 02 2013, translated from Pab Ter's Maple program *)

%Y Cf. A028445, A038952, A082379, A082380.

%K nonn,easy,nice

%O 0,2

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

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