cp's OEIS Frontend

A192296 Number of ternary words of length 2n obtained by self-shuffling.

%I A192296 #33 Jan 03 2021 09:52:24
%S A192296 1,3,15,93,621,4425,32703,248901,1934007,15285771,122437215,991731999,
%T A192296 8107830597
%N A192296 Number of ternary words of length 2n obtained by self-shuffling.
%C A192296 See A191755 for the number of binary words of length 2n obtained by self-shuffling and also for an explanation of "self-shuffling" and a reference.
%H A192296 N. Rampersad and J. Shallit, <a href="http://arxiv.org/abs/1106.5767">Shuffling and unshuffling</a>, preprint, arXiv:1106.5767 [cs.FL], 2011.
%e A192296 a(2) = 15 because {0,0,0,0}, {0,0,1,1}, {0,0,2,2}, {0,1,0,1}, {0,2,0,2}, {1,0,1,0}, {1,1,0,0}, {1,1,1,1}, {1,1,2,2}, {1,2,1,2}, {2,0,2,0}, {2,1,2,1}, {2,2,0,0}, {2,2,1,1}, {2,2,2,2} (and no other ternary words of length 4) are generated by self-shuffling.
%o A192296 (Python)
%o A192296 from itertools import product, combinations
%o A192296 def a(n):
%o A192296   if n<=1: return 3**n
%o A192296   range2n, set2n = list(range(2*n)), set(range(2*n))
%o A192296   allset, ssw = set(), [0 for i in range(2*n)]
%o A192296   for w in product("012", repeat=n-1):
%o A192296     w = "0" + "".join(w)
%o A192296     if w.count("1") > w.count("2"): continue
%o A192296     for s in combinations(range2n, n):
%o A192296       nots = sorted(set2n-set(s))
%o A192296       for i, c in enumerate(w): ssw[s[i]] = ssw[nots[i]] = c
%o A192296       allset.add("".join(ssw))
%o A192296   num2g1 = sum(w.count("1") < w.count("2") for w in allset)
%o A192296   return 3*(len(allset) + num2g1)
%o A192296 print([a(n) for n in range(8)]) # _Michael S. Branicky_, Jan 03 2021
%Y A192296 Cf. A191755.
%K A192296 nonn,more
%O A192296 0,2
%A A192296 _John W. Layman_, Jun 27 2011
%E A192296 a(8)-a(9) from _Alois P. Heinz_, Sep 26 2011
%E A192296 a(10)-a(12) from _Bert Dobbelaere_, Oct 02 2018