A096168 Number of Abelian cubefree words over a 3-letter alphabet.

1, 3, 9, 24, 66, 180, 468, 1206, 3150, 7998, 20124, 50520, 124044, 303906, 744870, 1790226, 4319322, 10432044, 24926934, 59570514, 142662384, 339247320, 807092274, 1920506232, 4543861644

Offset

0,2

Comments

An abelian cube is three consecutive blocks that are anagrams (rearrangements) of each other, such as (012)(120)(102).

For n > 1, a(n) is a multiple of 3 by symmetry. - Michael S. Branicky, Jul 11 2021

Links

Table of n, a(n) for n=0..24.

A. Aberkane, J. D. Currie and N. Rampersad, The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially, J. Integer Sequences, Article 04.2.7, 2004.

A. V. Samsonov and A. M. Shur, On Abelian repetition threshold, RAIRO-Theor. Inf. Appl. 46 (2012) 147-163.

Formula

Let L = lim a(n)^(1/n); then L exists since a(n) is submultiplicative. L > 2^(1/24) (Aberkane, Currie, Rampersad 2004), L < 2.371237 (Samsonov, Shur 2012). No good empirical guess for L is known. - Arseny Shur, Apr 27 2015

A305595(n) <= a(n) <= A051042(n). - Michael S. Branicky, Jul 11 2021

Example

a(3) = 24, since the only Abelian cubes of length 3 are 000, 111, 222.

Prog

(Python)
from itertools import product
def anagrams(b1, b2, b3):
    return sorted(b1) == sorted(b2) == sorted(b3)
def acf(s):
    for l in range(1, len(s)//3 + 1):
      for i in range(len(s) - 3*l + 1):
          if anagrams(s[i:i+l], s[i+l:i+2*l], s[i+2*l:i+3*l]): return False
    return True
def a(n):
    if n == 0: return 1
    return 3*sum(acf("0"+"".join(w)) for w in product("012", repeat=n-1))
print([a(n) for n in range(14)]) # Michael S. Branicky, Jul 11 2021
(Python) # faster, but > memory, version for initial segment of sequence
def anagrams(b1, b2, b3): return sorted(b1) == sorted(b2) == sorted(b3)
def iacf(s): # incrementally abelian cubefree
    for l in range(1, len(s)//3 + 1):
        if anagrams(s[-3*l:-2*l], s[-2*l:-l], s[-l:]): return False
    return True
def aupton(nn, verbose=False):
    alst, acfs = [1], set("0")
    for n in range(1, nn+1):
        an = 3*len(acfs)
        acfsnew = set(c+i for c in acfs for i in "012" if iacf(c+i))
        alst, acfs = alst+[an], acfsnew
        if verbose: print(n, an)
    return alst
print(aupton(14)) # Michael S. Branicky, Jul 22 2021

Crossrefs

Cf. A051042, A305595.

Sequence in context: A064831 A153582 A269461 * A051042 A121907 A179176

Adjacent sequences: A096165 A096166 A096167 * A096169 A096170 A096171

Keyword

nonn,hard,more

Author

Jeffrey Shallit, Jun 19 2004

Extensions

More terms from Jeffrey Shallit, May 23 2018

a(19)-a(21) from Michael S. Branicky, Jul 22 2021

a(22)-a(24) from Michael S. Branicky, Mar 25 2023

Status

approved