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

%I #26 Jan 27 2024 18:35:30

%S 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 76,83,89,95,100,108,114,122

%N Maximum possible number of distinct 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.

%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 = 5 the maximum is achieved by the word 00110, which has the abelian squares 00, 11, 0110.

%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 return max(sum(s in w for s in abel_squares) for w in words)

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

%K nonn,hard,more

%O 1,4

%A _Jeffrey Shallit_, Sep 16 2015

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