A242949 Number of distinct ternary squarefree words of length 2n that can be obtained as the self-shuffle of a ternary squarefree word of length n.

0, 0, 6, 12, 30, 24, 42, 78, 138, 228, 396, 588, 1008, 1494, 2634

Offset

1,3

Comments

"squarefree" means it contains no block of the form xx, with x nonempty. A length-2n word w is in the self-shuffle of a length-n word x if there is a disjoint partition of the indices {1,2,..., 2n} into two increasing sequences of length n, say s and t, such that x = w[s] = w[t].

Links

Table of n, a(n) for n=1..15.

T. Harju and M. Müller, Square-free shuffles of words, arxiv preprint arXiv:1309.2137 [cs.DM], 2013, Table 3, page 7.

Example

a(3) = 6, as the sequences are 010212 (arising from self-shuffle of 012), and the 5 others arising from permutation of the letters 0, 1, 2.

Prog

(Python)
from itertools import product, combinations
def issquarefree(s):
    for l in range(1, len(s)//2 + 1):
        for i in range(len(s)-2*l+1):
            if s[i:i+l] == s[i+l:i+2*l]: return False
    return True
def squarefree(n): # all length n squarefree ternary words starting with "0"
    if n == 0: yield ""; return
    if n == 1: yield "0"; return
    squares = ["".join(u) + "".join(u)
      for r in range(1, n//2 + 1) for u in product("012", repeat = r)]
    words = ("0"+"".join(w) for w in product("012", repeat=n-1))
    yield from [w for w in words if all(s not in w for s in squares)]
def a(n):
    range2n, set2n = list(range(2*n)), set(range(2*n))
    allset, ssw = set(), [0 for i in range(2*n)]
    for w in squarefree(n):
        if w.count("1") > w.count("2"): continue
        for s in combinations(range2n, n):
            nots = sorted(set2n-set(s))
            for i, c in enumerate(w): ssw[s[i]] = ssw[nots[i]] = c
            t = "".join(ssw)
            if issquarefree(t): allset.add(t)
    num2g1 = sum(w.count("1") < w.count("2") for w in allset)
    return 3*(len(allset) + num2g1)
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Aug 16 2021

Crossrefs

Sequence in context: A294730 A079390 A124679 * A341637 A143272 A153877

Adjacent sequences: A242946 A242947 A242948 * A242950 A242951 A242952

Keyword

nonn,more

Author

Jeffrey Shallit, May 27 2014

Extensions

a(12) corrected by and a(14)-a(15) from Michael S. Branicky, Aug 16 2021

Status

approved