login
A305003
Number of length-n binary words having no subwords that are abelian fourth powers.
2
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
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).
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: A317884 A365253 A054193 * A117633 A308148 A273154
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, May 23 2018
STATUS
approved