|
%I #30 Jan 27 2024 18:51:37
%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
|
