login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A262265 Maximum possible number of inequivalent abelian squares occurring in a binary word of length n 1
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 (list; graph; refs; listen; history; text; internal format)
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 contains 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 25 23:39 EDT 2021. Contains 346294 sequences. (Running on oeis4.)