(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)
|