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

Author

Jeffrey Shallit, Sep 16 2015

Keywords

• nonn
• hard
• more

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.

Examples

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

Links

• 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.

Programs

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

Extensions

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