cp's OEIS Frontend

A262249 Maximum possible number of distinct abelian squares occurring in a binary word of length n.

%I A262249 #26 Jan 27 2024 18:35:30
%S A262249 0,1,1,2,3,4,5,7,9,11,13,15,17,21,23,26,30,34,38,43,47,52,57,62,65,71,
%T A262249 76,83,89,95,100,108,114,122
%N A262249 Maximum possible number of distinct abelian squares occurring in a binary word of length n.
%C A262249 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.
%H A262249 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 A262249 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 A262249 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 A262249 For n = 5 the maximum is achieved by the word 00110, which has the abelian squares 00, 11, 0110.
%o A262249 (Python)
%o A262249 from itertools import product, permutations
%o A262249 def a(n): # only check words starting with 0 by symmetry
%o A262249   ar = ("".join(u) for r in range(1, n//2+1) for u in product("01", repeat=r))
%o A262249   abel_squares = set(w+"".join(wp) for w in ar for wp in permutations(w))
%o A262249   words = ("0"+"".join(w) for w in product("10", repeat=n-1))
%o A262249   return max(sum(s in w for s in abel_squares) for w in words)
%o A262249 print([a(n) for n in range(1, 14)]) # _Michael S. Branicky_, Dec 20 2020
%K A262249 nonn,hard,more
%O A262249 1,4
%A A262249 _Jeffrey Shallit_, Sep 16 2015
%E A262249 a(17)-a(34) from _Lars Blomberg_, Feb 04 2016