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

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

Offset

1,4

Comments

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.

Links

Table of n, a(n) for n=1..34.

Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walén, Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word, Slides, DLT 2014.

Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walén, Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word, in A. M. Shur and M. V. Volkov (Eds.): DLT 2014, LNCS 8633, Springer, pp. 215-226, 2014.

Jamie Simpson, Solved and unsolved problems about abelian squares, arXiv:1802.04481 [math.CO], 2018.

Example

For n = 5 the maximum is achieved by the word 00110, which has the abelian squares 00, 11, 0110.

Prog

(Python)
from itertools import product, permutations
def a(n): # only check words starting with 0 by symmetry
  ar = ("".join(u) for r in range(1, n//2+1) for u in product("01", repeat=r))
  abel_squares = set(w+"".join(wp) for w in ar for wp in permutations(w))
  words = ("0"+"".join(w) for w in product("10", repeat=n-1))
  return max(sum(s in w for s in abel_squares) for w in words)
print([a(n) for n in range(1, 14)]) # Michael S. Branicky, Dec 20 2020

Crossrefs

Sequence in context: A051532 A325461 A135785 * A248421 A008732 A130520

Adjacent sequences: A262246 A262247 A262248 * A262250 A262251 A262252

Keyword

nonn,hard,more

Author

Jeffrey Shallit, Sep 16 2015

Extensions

a(17)-a(34) from Lars Blomberg, Feb 04 2016

Status

approved