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

1, 2, 6, 22, 82, 320, 1268, 5102, 20632, 83972, 342468, 1399296, 5720966, 23396618, 95654386, 390868900, 1596000418, 6511211718, 26538617050, 108060466284

Offset

0,2

Comments

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.

See A192296 for the number of ternary words of length 2n obtained by self-shuffling.

All terms after a(0) are even by symmetry. # Michael S. Branicky, Sep 28 2021

Links

Table of n, a(n) for n=0..19.

J. Erickson, How hard is unshuffling a string?, August 16 2010. See in particular comment by "Radu GRIGore", Aug 20 2010 at 7:53.

Samuele Giraudo and S. Vialette, Unshuffling Permutations, arXiv preprint arXiv:1601.05962 [cs.DS], 2016.

Jarosław Grytczuk, Bartłomiej Pawlik, and Mariusz Pleszczyński, Variations on shuffle squares, arXiv:2308.13882 [math.CO], 2023. See p. 11.

Xiaoyu He, Emily Huang, Ihyun Nam and Rishubh Thaper, Shuffle Squares and Reverse Shuffle Squares, arXiv:2109.12455 [math.CO], 2021.

D. Henshall, N. Rampersad, and J. Shallit, Shuffling and unshuffling, arXiv:1106.5767 [cs.FL], 2011.

D. Henshall, N. Rampersad, and J. Shallit, Shuffling and unshuffling, Bull. EATCS, No. 107, June 2012, pp. 131-142.

Example

a(2) = 6 because {0000, 0011, 0101, 1010, 1100, 1111} are all generated by self-shuffling.

Prog

(Python)
from itertools import product, combinations
def a(n): # returns A191755(n), A331850(n), least argmax for A331850(n)
    if n<=1: return 2**n, 1, '0'*n
    range2n, set2n = list(range(2*n)), set(range(2*n))
    allset, mx, argmx, ssw = set(), -1, None, [0 for i in range(2*n)]
    for w in product("01", repeat=n-1):
        w, sswset = "0" + "".join(w), set()
        for s in combinations(range2n, n):
            nots = sorted(set2n-set(s))
            for i, c in enumerate(w): ssw[s[i]] = ssw[nots[i]] = c
            sswset.add("".join(ssw))
        allset |= sswset
        if len(sswset) > mx: mx, argmx = len(sswset), w
    return 2*len(allset), mx, argmx
print([a(n)[0] for n in range(9)]) # Michael S. Branicky, Sep 28 2021

Crossrefs

Cf. A192296, A279200 (square permutations), A360412.

Sequence in context: A150230 A360266 A360290 * A150231 A150232 A150233

Adjacent sequences: A191752 A191753 A191754 * A191756 A191757 A191758

Keyword

nonn,hard,more,nice

Author

Jeffrey Shallit, Jun 15 2011

Extensions

a(0)-a(9) confirmed and a(10)-a(13) added by John W. Layman, Jun 28 2011

a(0)-a(13) confirmed by Joerg Arndt, Jul 13 2011

Added a(14) and a(15), Joerg Arndt, Jul 18 2011

Added a(16), Joerg Arndt, Feb 04 2017

Added a(17)-a(19) and confirmed a(14)-a(16), Bert Dobbelaere, Oct 02 2018

Status

approved