|
%I #19 Aug 16 2021 14:53:36
%S 0,0,6,12,30,24,42,78,138,228,396,588,1008,1494,2634
%N 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.
%C "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].
%H T. Harju and M. Müller, <a href="http://arxiv.org/abs/1309.2137">Square-free shuffles of words</a>, arxiv preprint arXiv:1309.2137 [cs.DM], 2013, Table 3, page 7.
%e 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.
%o (Python)
%o from itertools import product, combinations
%o def issquarefree(s):
%o for l in range(1, len(s)//2 + 1):
%o for i in range(len(s)-2*l+1):
%o if s[i:i+l] == s[i+l:i+2*l]: return False
%o return True
%o def squarefree(n): # all length n squarefree ternary words starting with "0"
%o if n == 0: yield ""; return
%o if n == 1: yield "0"; return
%o squares = ["".join(u) + "".join(u)
%o for r in range(1, n//2 + 1) for u in product("012", repeat = r)]
%o words = ("0"+"".join(w) for w in product("012", repeat=n-1))
%o yield from [w for w in words if all(s not in w for s in squares)]
%o def a(n):
%o range2n, set2n = list(range(2*n)), set(range(2*n))
%o allset, ssw = set(), [0 for i in range(2*n)]
%o for w in squarefree(n):
%o if w.count("1") > w.count("2"): continue
%o for s in combinations(range2n, n):
%o nots = sorted(set2n-set(s))
%o for i, c in enumerate(w): ssw[s[i]] = ssw[nots[i]] = c
%o t = "".join(ssw)
%o if issquarefree(t): allset.add(t)
%o num2g1 = sum(w.count("1") < w.count("2") for w in allset)
%o return 3*(len(allset) + num2g1)
%o print([a(n) for n in range(1, 10)]) # _Michael S. Branicky_, Aug 16 2021
%K nonn,more
%O 1,3
%A _Jeffrey Shallit_, May 27 2014
%E a(12) corrected by and a(14)-a(15) from _Michael S. Branicky_, Aug 16 2021
| 