A305003 Number of length-n binary words having no subwords that are abelian fourth powers.

1, 2, 4, 8, 14, 26, 48, 88, 146, 236, 394, 674, 1060, 1640, 2536, 4086, 6470, 10292, 16374, 25720, 39332, 60154, 92486, 144218, 217772, 327898, 494384, 745096, 1089186, 1587432, 2338018, 3460572, 4977860, 7197148, 10395464, 14991916, 20924630, 28852352

Offset

0,2

Comments

An "abelian fourth power" means four contiguous nonempty blocks of the same length and same number of 0's and 1's, such as (011)(101)(110)(101).

Links

Lucas Mol, Table of n, a(n) for n = 0..50

James D. Currie, The number of binary words avoiding abelian fourth powers grows exponentially, Theoretical Computer Science 319 (2004) 441-446. Proves that the number of such words exceeds 2^{(n-15)/16}.

James D. Currie, Lucas Mol, Narad Rampersad, and Jeffrey Shallit, Extending Dekking's construction of an infinite binary word avoiding abelian 4-powers. Proves that the number of such words of length n is Omega(1.172^n).

Lucas Mol, Python 3 program for computing a(n) for n = 2..50.

Example

For n = 5 the only words not counted are 00000, 00001, 10000, and their complements.

Maple

f:= proc(L)
local i, w, j;
for i from 1 to floor(nops(L)/4) do
   if L[2*i]=2*L[i] and L[3*i]=3*L[i] and L[4*i]=4*L[i] then return NULL
   fi
od:
L
end proc:
g:= proc(L)
  local Lp;
  Lp:= [0, op(L)]:
  f(Lp), f(map(`+`, Lp, 1));
end proc:
S:= [0]: A[0]:= 1: A[1]:= 2:for n from 2 to 31 do
  S:= map(g, S);
  A[n]:= 2*nops(S);
od:
seq(A[i], i=0..31); # Robert Israel, May 23 2018

Crossrefs

Sequence in context: A378196 A365253 A054193 * A117633 A308148 A273154

Adjacent sequences: A305000 A305001 A305002 * A305004 A305005 A305006

Keyword

nonn

Author

Jeffrey Shallit, May 23 2018

Status

approved