

A191755


Number of square binary words: binary words of length 2n obtained by selfshuffling.


3



1, 2, 6, 22, 82, 320, 1268, 5102, 20632, 83972, 342468, 1399296, 5720966, 23396618, 95654386, 390868900, 1596000418, 6511211718, 26538617050, 108060466284
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Selfshuffle means shuffle of word with itself, and shuffle means "notnecessarilyperfect shuffle". In other words, the shuffle of two strings x and y is the set of strings obtained by scanning lefttoright 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 selfshuffling.


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, S. Vialette, Unshuffling Permutations, arXiv preprint arXiv:1601.05962 [cs.DS], 2016.
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. 131142.


EXAMPLE

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


CROSSREFS

Cf. A192296, A279200 (square permutations).
Sequence in context: A072547 A150229 A150230 * 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



