cp's OEIS Frontend

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

%I A262265 #33 Nov 16 2024 02:01:45
%S A262265 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 A262265 29,31,32,34,36,37,39,41
%N A262265 Maximum possible number of inequivalent abelian squares occurring in a binary word of length n.
%C A262265 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 A262265 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 A262265 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 A262265 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 A262265 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 A262265 (Python)
%o A262265 from itertools import product, permutations
%o A262265 def a(n): # only check words starting with 0 by symmetry
%o A262265   ar = ("".join(u) for r in range(1, n//2+1) for u in product("01", repeat=r))
%o A262265   abel_squares = set(w+"".join(wp) for w in ar for wp in permutations(w))
%o A262265   words = ("0"+"".join(w) for w in product("10", repeat=n-1))
%o A262265   maxn = -1
%o A262265   for w in words:
%o A262265     seen = set()
%o A262265     for s in abel_squares:
%o A262265       if s in w: seen.add(tuple(sorted(s)))
%o A262265     maxn = max(maxn, len(seen))
%o A262265   return maxn
%o A262265 print([a(n) for n in range(1, 14)]) # _Michael S. Branicky_, Dec 20 2020
%Y A262265 Cf. A262249.
%K A262265 nonn,hard,more
%O A262265 1,4
%A A262265 _Jeffrey Shallit_, Sep 17 2015
%E A262265 a(18)-a(34) from _Lars Blomberg_, Feb 04 2016