A192296 -id:A192296 - cp's OEIS frontend

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

Jeffrey Shallit, Jun 15 2011

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

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

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.

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

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

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

A193020 Number of distinct self-shuffles of the word given by the binary representation of n.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 3, 1, 4, 9, 8, 6, 6, 6, 4, 1, 5, 16, 18, 18, 13, 16, 18, 8, 10, 18, 13, 9, 10, 8, 5, 1, 6, 25, 32, 40, 27, 40, 54, 30, 19, 40, 32, 27, 37, 36, 32, 10, 15, 40, 37, 36, 24, 27, 27, 12, 20, 30, 19, 12, 15, 10, 6, 1, 7, 36, 50, 75, 48, 77, 120

Offset: 0

John W. Layman, Jul 14 2011

nonn

See Jeffrey Shallit's A191755 for the definition of self-shuffle and a link to a preprint of the paper "Shuffling and Unshuffling".

An examination of the terms of the sequence leads to the following conjectures (in each case with the caveat that k must exceed a certain lower bound): a(2^k-5)=3k-6, a(2^k-4)=k*(k-1)/2, a(2^k-3)=2k-2, a(2^k-2)=k, a(2^k-1)=1, a(2^k)=k+1, a(2^k+1)=k^2, a(2^k+2)=2*(k-1)^2, a(2^k+3)=k*(k-1)^2/2. To illustrate, consider a(2^k+1); we get, for k=1, 2, 3, ..., a(3)=1, a(5)=4, a(9)=9, a(17)=16, a(33)=25, a(65)=36, a(129)=49, a(257)=64,..., leading to the conjecture that a(2^k+1)=k^2. The other conjectures were arrived at in the same manner.

			The binary representation of n=9 is 1001, which has the nine distinct self-shuffles 1'0'0'1001'1, 1'0'0'101'01, 1'0'0'1'1001, 1'0'10'001'1, 1'0'10'01'01, 1'0'10'1'001, 1'10'0'001'1, 1'10'0'01'01, 1'10'0'1'001 (although 1' is identical to 1, and similarly for 0' and 0, the apostrophes indicate one way in which the digits may be assigned to the two copies of the word 1001 and 1'0'0'1' before self-shuffling).  Thus a(9)=9.

Alois P. Heinz, Table of n, a(n) for n = 0..2048

Cf. A191755, A192296.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions