login

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

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

%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