login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of binary strings of length n that are "weak abelian squares".
0

%I #22 Jan 27 2016 09:15:50

%S 0,2,2,6,2,36,2,94,128,476,2,2044,2,6600,12200,21326,2,114180,2,

%T 420196,611400,1377272,2,6880524,5162552,20385176,27057260,93466916,2,

%U 449091204,2,1191408430,1752427686,4596497100,8832507602,27711558964,2,69735250200,98612948480

%N Number of binary strings of length n that are "weak abelian squares".

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

%H Sergey Avgustinovich and Svetlana Puzynina, <a href="http://arxiv.org/abs/1302.4359">Weak abelian periodicity of infinite words</a>, preprint, 18 Feb 2013, arXiv:1302.4359 [math.CO].

%e The weak abelian squares of length 4 are 0000, 0101, 0110, 1001, 1010, 1111. Therefore a(4)=6.

%o (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 */

%K nonn

%O 1,2

%A _Jeffrey Shallit_, Oct 16 2013

%E a(22)-a(39) from _Lars Blomberg_, Jan 27 2016