A343421 Number of Dean words of length n, i.e., squarefree reduced words over {0,1,2,3}.

4, 8, 16, 24, 40, 64, 104, 144, 216, 328, 496, 720, 1072, 1584, 2344, 3384, 4952, 7264, 10632, 15504, 22656, 33136, 48488, 70592, 103032, 150352, 219400, 319816, 466664, 680872, 993440, 1447952, 2111448, 3079464, 4491216, 6548936, 9550728, 13927840, 20311168

Offset: 1

Author

Michel Marcus, Apr 15 2021

Keywords

• nonn

Comments

A Dean word is a reduced word that does not contain occurrences of ww for any nonempty w.

a(n) is a multiple of 4 by symmetry. - Michael S. Branicky, Jun 20 2022

Links

• Martin Ehrenstein, Table of n, a(n) for n = 1..64
• Richard A. Dean, A sequence without repeats on x, x^{-1}, y, y^{-1}, Amer. Math. Monthly 72, 1965. pp. 383-385. MR 31 #350.
• Tero Harju, Avoiding Square-Free Words on Free Groups, arXiv:2104.06837 [math.CO], 2021.

Crossrefs

Cf. A003324, A112658, A051041.

Programs

Python

def isf(s): # incrementally squarefree (check factors ending in last letter)
    for l in range(1, len(s)//2 + 1):
        if s[-2*l:-l] == s[-l:]: return False
    return True
def aupton(nn, verbose=False):
    alst, sfs = [], set("0")
    for n in range(1, nn+1):
        an, eo = 4*len(sfs), ["02", "13"]
        sfsnew = set(s+i for s in sfs for i in eo[n%2] if isf(s+i))
        alst, sfs = alst+[an], sfsnew
        if verbose: print(n, an)
    return alst
print(aupton(30)) # Michael S. Branicky, Jun 20 2022

Extensions

More terms from James Rayman, Apr 15 2021