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

Author

Jeffrey Shallit, May 23 2018

Keywords

• nonn

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

Examples

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

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.

Programs

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