login
A230266
Number of binary strings of length n that are "weak abelian squares".
0
0, 2, 2, 6, 2, 36, 2, 94, 128, 476, 2, 2044, 2, 6600, 12200, 21326, 2, 114180, 2, 420196, 611400, 1377272, 2, 6880524, 5162552, 20385176, 27057260, 93466916, 2, 449091204, 2, 1191408430, 1752427686, 4596497100, 8832507602, 27711558964, 2, 69735250200, 98612948480
OFFSET
1,2
COMMENTS
A weak abelian square is a word w that can be written as x x' for nonempty strings x, x' such that the relative frequency of occurrences of each letter is the same in the blocks x and x'. For example, 011100 is a weak abelian square, as it can be written (01)(1100) and in each block both 0 and 1 occur 50% of the time.
LINKS
Sergey Avgustinovich and Svetlana Puzynina, Weak abelian periodicity of infinite words, preprint, 18 Feb 2013, arXiv:1302.4359 [math.CO].
EXAMPLE
The weak abelian squares of length 4 are 0000, 0101, 0110, 1001, 1010, 1111. Therefore a(4)=6.
PROG
(PARI) a(n)=s=0; for(m=0, 2^n-1, b=binary(m); bl=#b; b=vector(n, i, if(i<=n-bl, 0, b[i-(n-bl)])); h=hammingweight(b); bl=#b; ss=0; for(i=1, bl-1, ss=ss+b[i]; if(ss/i==(h-ss)/(bl-i), s=s+1; break))); s /* Ralf Stephan, Oct 17 2013 */
CROSSREFS
Sequence in context: A293214 A293216 A319708 * A342628 A329380 A348146
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Oct 16 2013
EXTENSIONS
a(22)-a(39) from Lars Blomberg, Jan 27 2016
STATUS
approved