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
T. Harju and M. Müller, Square-free shuffles of words, arxiv preprint arXiv:1309.2137 [cs.DM], 2013, Table 3, page 7.
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(w); break
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
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, May 27 2014
EXTENSIONS
a(14)-a(16) from Michael S. Branicky, Aug 16 2021
STATUS
approved