cp's OEIS Frontend

A268084 Minimum number of occurrences of abelian squares in a binary word of length n.

%I A268084 #31 Dec 21 2020 01:54:52
%S A268084 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 A268084 32,34,35,37,39,41,43,44
%N A268084 Minimum number of occurrences of abelian squares in a binary word of length n.
%C A268084 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 A268084 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 A268084 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 A268084 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 A268084 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 A268084 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 A268084 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 A268084 (Python)
%o A268084 from itertools import product, permutations
%o A268084 def count_overlaps(subs, s):
%o A268084   c = i = 0
%o A268084   while i != -1:
%o A268084     i = s.find(subs, i)
%o A268084     if i != -1: c += 1; i += 1
%o A268084   return c
%o A268084 def a(n): # only check words starting with 0 by symmetry
%o A268084   ar = ("".join(u) for r in range(1, n//2+1) for u in product("01",
%o A268084 repeat=r))
%o A268084   abel_squares = set(w+"".join(wp) for w in ar for wp in permutations(w))
%o A268084   words = ("0"+"".join(w) for w in product("10", repeat=n-1))
%o A268084   themin = n*n
%o A268084   for w in words:
%o A268084     numw = 0
%o A268084     for s in abel_squares:
%o A268084       numw += count_overlaps(s, w)
%o A268084       if numw >= themin: break
%o A268084     else: themin = min(themin, numw)
%o A268084   return themin
%o A268084 print([a(n) for n in range(1, 14)]) # _Michael S. Branicky_, Dec 20 2020
%Y A268084 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 A268084 nonn,more
%O A268084 1,5
%A A268084 _Jamie Simpson_, Jan 26 2016
%E A268084 a(21)-a(35) from _Lars Blomberg_, Feb 04 2016