A323487 Number of length-n ternary words that are bi-maximally squarefree.

0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 18, 0, 24, 0, 48, 42, 18, 12, 48, 78, 36, 66, 108, 102, 240, 222, 360, 330, 696, 690, 858, 1086, 1692, 1920, 2604, 3156, 4284, 5370, 7308, 9270, 12036, 15756, 20688, 26562, 34500, 44274, 59058, 75576

Offset: 1

Author

Jeffrey Shallit, Jan 16 2019

Keywords

• nonn

Comments

A word is squarefree if it contains no block of the form XX, where X is a nonempty block. A word is bi-maximally squarefree if it cannot be extended on either the left or right to a longer squarefree word.

All terms are multiples of 6 due to possible renamings of letters. - Michael S. Branicky, Sep 01 2021

Examples

			For n = 7 the six possibilities are 0102010 and all renamings of the letters.
For n = 15 the six possibilities are 010210120102101 and all renamings of the letters.
		

Crossrefs

Cf. A282212, which is the one-sided version of maximally squarefree.

Programs

Python

def isf(w): # incrementally squarefree (check factors ending in last letter)
    for l in range(1, len(w)//2 + 1):
        if w[-2*l:-l] == w[-l:]: return False
    return True
def is_bmsf(w, sfsnew): # is w bi-maximally squarefree
    lefts, rights = [c+w for c in "123"], [w+c for c in "123"]
    return all(x not in sfsnew for x in lefts + rights)
def aupton(nn):
    alst, sfs = [], set("123")
    for n in range(1, nn+1):
        sfsnew = set(w+c for w in sfs for c in "123" if isf(w+c))
        an = len([w for w in sfs if is_bmsf(w, sfsnew)])
        alst.append(an)
        sfs = sfsnew
    return alst
print(aupton(30)) # Michael S. Branicky, Sep 01 2021

Extensions

a(31)-a(58) from Michael S. Branicky, Sep 01 2021