

A262265


Maximum possible number of inequivalent abelian squares occurring in a binary word of length n


1



0, 1, 1, 2, 3, 4, 4, 6, 6, 7, 8, 10, 10, 11, 12, 15, 16, 17, 17, 19, 21, 22, 23, 25, 26, 28, 29, 31, 32, 34, 36, 37, 39, 41
(list;
graph;
refs;
listen;
history;
text;
internal format)



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

Table of n, a(n) for n=1..34.
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. 215226, 2014.
Jamie Simpson, Solved and unsolved problems about abelian squares, arXiv:1802.04481 [math.CO], 2018.


EXAMPLE

For n = 7 the word contains 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=n1))
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

Cf. A262249.
Sequence in context: A337125 A063208 A343912 * A227683 A321166 A092988
Adjacent sequences: A262262 A262263 A262264 * A262266 A262267 A262268


KEYWORD

nonn,hard,more


AUTHOR

Jeffrey Shallit, Sep 17 2015


EXTENSIONS

a(18)a(34) from Lars Blomberg, Feb 04 2016


STATUS

approved



