Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #31 Dec 21 2020 01:54:52
%S 0,0,0,1,2,3,4,4,5,6,7,8,10,11,12,14,15,17,18,20,21,23,24,26,28,29,30,
%T 32,34,35,37,39,41,43,44
%N Minimum number of occurrences of abelian squares in a binary word of length n.
%C A binary word is a sequence each member of which belongs to an alphabet of size 2 such as {a,b}. An abelian square is an even length factor whose first half is an anagram of the second half, for example abaaaaab.
%C One can also ask for the minimum number of distinct abelian squares in a word of length n and the minimum number of nonequivalent abelian squares. Two abelian squares are equivalent if they are anagrams of each other.
%C For example the word ababbaaabaa contains 5 distinct abelian squares, aa, bb, abab, abba and baaaba, but only 4 nonequivalent abelian squares since abab and abba are equivalent. It's conjectured that both the minimum number of distinct abelian squares in a binary word of length n and the minimum number of nonequivalent abelian squares equal floor(n/4)
%D G. Fici and A. Saarela, On the minimum number of abelian squares in a word, Combinatorics and Algorithmics of Strings, Dagstuhl Reports, 4(2014), pages 34-35.
%H A. S. Fraenkel, J. Simpson, and M. Paterson, <a href="http://dx.doi.org/10.1007/3-540-63220-4_51">On weak circular squares in binary words</a>, Combinatorial Pattern Matching, Springer Berlin Heidelberg, 1997, pages 76-82.
%H Jamie Simpson, <a href="https://arxiv.org/abs/1802.04481">Solved and unsolved problems about abelian squares</a>, arXiv:1802.04481 [math.CO], 2018.
%e For example the least number of occurrences of abelian squares in a binary word of length 11 is 7. There are 12 words which attain this minimum. One is ababbaaabaa which contains 3 occurrences of aa and one each of bb, abab, abba and baaaba.
%o (Python)
%o from itertools import product, permutations
%o def count_overlaps(subs, s):
%o c = i = 0
%o while i != -1:
%o i = s.find(subs, i)
%o if i != -1: c += 1; i += 1
%o return c
%o def a(n): # only check words starting with 0 by symmetry
%o ar = ("".join(u) for r in range(1, n//2+1) for u in product("01",
%o repeat=r))
%o abel_squares = set(w+"".join(wp) for w in ar for wp in permutations(w))
%o words = ("0"+"".join(w) for w in product("10", repeat=n-1))
%o themin = n*n
%o for w in words:
%o numw = 0
%o for s in abel_squares:
%o numw += count_overlaps(s, w)
%o if numw >= themin: break
%o else: themin = min(themin, numw)
%o return themin
%o print([a(n) for n in range(1, 14)]) # _Michael S. Branicky_, Dec 20 2020
%Y A262249 gives the maximum number of distinct abelian squares in a binary word of length n and A262265 gives the maximum number of nonequivalent abelian squares.
%K nonn,more
%O 1,5
%A _Jamie Simpson_, Jan 26 2016
%E a(21)-a(35) from _Lars Blomberg_, Feb 04 2016