cp's OEIS Frontend

A191755 Number of square binary words: binary words of length 2n obtained by self-shuffling.

%I A191755 #71 Aug 31 2023 11:02:12
%S A191755 1,2,6,22,82,320,1268,5102,20632,83972,342468,1399296,5720966,
%T A191755 23396618,95654386,390868900,1596000418,6511211718,26538617050,
%U A191755 108060466284
%N A191755 Number of square binary words: binary words of length 2n obtained by self-shuffling.
%C A191755 Self-shuffle means shuffle of word with itself, and shuffle means "not-necessarily-perfect shuffle".  In other words, the shuffle of two strings x and y is the set of strings obtained by scanning left-to-right through the strings, choosing arbitrarily at each step a symbol from x or y.
%C A191755 See A192296 for the number of ternary words of length 2n obtained by self-shuffling.
%C A191755 All terms after a(0) are even by symmetry. # _Michael S. Branicky_, Sep 28 2021
%H A191755 J. Erickson, <a href="http://cstheory.stackexchange.com/questions/34/how-hard-is-unshuffling-a-string">How hard is unshuffling a string?</a>, August 16 2010. See in particular comment by "Radu GRIGore", Aug 20 2010 at 7:53.
%H A191755 Samuele Giraudo and S. Vialette, <a href="https://arxiv.org/abs/1601.05962">Unshuffling Permutations</a>, arXiv preprint arXiv:1601.05962 [cs.DS], 2016.
%H A191755 Jarosław Grytczuk, Bartłomiej Pawlik, and Mariusz Pleszczyński, <a href="https://arxiv.org/abs/2308.13882">Variations on shuffle squares</a>, arXiv:2308.13882 [math.CO], 2023. See p. 11.
%H A191755 Xiaoyu He, Emily Huang, Ihyun Nam and Rishubh Thaper, <a href="https://arxiv.org/abs/2109.12455">Shuffle Squares and Reverse Shuffle Squares</a>, arXiv:2109.12455 [math.CO], 2021.
%H A191755 D. Henshall, N. Rampersad, and J. Shallit, <a href="https://arxiv.org/abs/1106.5767">Shuffling and unshuffling</a>, arXiv:1106.5767 [cs.FL], 2011.
%H A191755 D. Henshall, N. Rampersad, and J. Shallit, <a href="http://bulletin.eatcs.org/index.php/beatcs/article/view/71">Shuffling and unshuffling</a>, Bull. EATCS, No. 107, June 2012, pp. 131-142.
%e A191755 a(2) = 6 because {0000, 0011, 0101, 1010, 1100, 1111} are all generated by self-shuffling.
%o A191755 (Python)
%o A191755 from itertools import product, combinations
%o A191755 def a(n): # returns A191755(n), A331850(n), least argmax for A331850(n)
%o A191755     if n<=1: return 2**n, 1, '0'*n
%o A191755     range2n, set2n = list(range(2*n)), set(range(2*n))
%o A191755     allset, mx, argmx, ssw = set(), -1, None, [0 for i in range(2*n)]
%o A191755     for w in product("01", repeat=n-1):
%o A191755         w, sswset = "0" + "".join(w), set()
%o A191755         for s in combinations(range2n, n):
%o A191755             nots = sorted(set2n-set(s))
%o A191755             for i, c in enumerate(w): ssw[s[i]] = ssw[nots[i]] = c
%o A191755             sswset.add("".join(ssw))
%o A191755         allset |= sswset
%o A191755         if len(sswset) > mx: mx, argmx = len(sswset), w
%o A191755     return 2*len(allset), mx, argmx
%o A191755 print([a(n)[0] for n in range(9)]) # _Michael S. Branicky_, Sep 28 2021
%Y A191755 Cf. A192296, A279200 (square permutations), A360412.
%K A191755 nonn,hard,more,nice
%O A191755 0,2
%A A191755 _Jeffrey Shallit_, Jun 15 2011
%E A191755 a(0)-a(9) confirmed and a(10)-a(13) added by _John W. Layman_, Jun 28 2011
%E A191755 a(0)-a(13) confirmed by _Joerg Arndt_, Jul 13 2011
%E A191755 Added a(14) and a(15), _Joerg Arndt_, Jul 18 2011
%E A191755 Added a(16), _Joerg Arndt_, Feb 04 2017
%E A191755 Added a(17)-a(19) and confirmed a(14)-a(16), _Bert Dobbelaere_, Oct 02 2018