A262265 - OEIS

%I #33 Nov 16 2024 02:01:45

%S 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,

%T 29,31,32,34,36,37,39,41

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

%C 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.

%H Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walén, <a href="http://dlt2014.sciencesconf.org/conference/dlt2014/pages/Session_6_Walen.pdf">Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word</a>, Slides, DLT 2014.

%H Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walén, <a href="http://mimuw.edu.pl/~kociumaka/files/dlt2014.pdf">Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word</a>, in A. M. Shur and M. V. Volkov (Eds.): DLT 2014, LNCS 8633, Springer, pp. 215-226, 2014.

%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 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.

%o (Python)

%o from itertools import product, permutations

%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", 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   maxn = -1

%o   for w in words:

%o     seen = set()

%o     for s in abel_squares:

%o       if s in w: seen.add(tuple(sorted(s)))

%o     maxn = max(maxn, len(seen))

%o   return maxn

%o print([a(n) for n in range(1, 14)]) # _Michael S. Branicky_, Dec 20 2020

%Y Cf. A262249.

%K nonn,hard,more

%O 1,4

%A _Jeffrey Shallit_, Sep 17 2015

%E a(18)-a(34) from _Lars Blomberg_, Feb 04 2016