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

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 = 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).

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))
  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

Crossrefs

Cf. A262249.

Sequence in context: A337125 A063208 A343912 * A227683 A321166 A092988

Adjacent sequences: A262262 A262263 A262264 * A262266 A262267 A262268

Keyword

nonn,hard,more

Author

Jeffrey Shallit, Sep 17 2015

Extensions

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

Status

approved