OFFSET
1,4
COMMENTS
An "abelian square" is a word of the form w w' where w' is a permutation of w, like the word "reappear". By "occurring" we mean occurring as a contiguous subword. Two abelian squares w w' and x x' are inequivalent if w is not a permutation of x.
LINKS
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walén, Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word, Slides, DLT 2014.
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walén, Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word, in A. M. Shur and M. V. Volkov (Eds.): DLT 2014, LNCS 8633, Springer, pp. 215-226, 2014.
Jamie Simpson, Solved and unsolved problems about abelian squares, arXiv:1802.04481 [math.CO], 2018.
EXAMPLE
For n = 7 the word 0011001 contains 5 distinct abelian squares (00, 11, 0110, 1001, 001100) but only 4 of these are inequivalent, since 0110 and 1001 are equivalent.
PROG
(Python)
from itertools import product, permutations
def a(n): # only check words starting with 0 by symmetry
ar = ("".join(u) for r in range(1, n//2+1) for u in product("01", repeat=r))
abel_squares = set(w+"".join(wp) for w in ar for wp in permutations(w))
words = ("0"+"".join(w) for w in product("10", repeat=n-1))
maxn = -1
for w in words:
seen = set()
for s in abel_squares:
if s in w: seen.add(tuple(sorted(s)))
maxn = max(maxn, len(seen))
return maxn
print([a(n) for n in range(1, 14)]) # Michael S. Branicky, Dec 20 2020
CROSSREFS
KEYWORD
nonn,hard,more,changed
AUTHOR
Jeffrey Shallit, Sep 17 2015
EXTENSIONS
a(18)-a(34) from Lars Blomberg, Feb 04 2016
STATUS
approved