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

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, 29, 31, 32, 34, 36, 37, 39, 41

Offset: 1

Author

Jeffrey Shallit, Sep 17 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. Two abelian squares w w' and x x' are inequivalent if w is not a permutation of x.

Examples

			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.
		

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.

Crossrefs

Cf. A262249.

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))
  maxn = -1
  for w in words:
    seen = set()
    for s in abel_squares:
      if s in w: seen.add(tuple(sorted(s)))
    maxn = max(maxn, len(seen))
  return maxn
print([a(n) for n in range(1, 14)]) # Michael S. Branicky, Dec 20 2020

Extensions

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