A331850 Largest cardinality of a set obtained by self-shuffling a binary word of length n.

1, 2, 4, 9, 18, 54, 120, 324, 900, 2406, 6400, 19600, 50176, 148042, 442325, 1373070, 3954113

Offset

1,2

Comments

The self-shuffle of a length-n word w is the set of all length-2n words that can be obtained by interleaving w with itself, as in the shuffle of a deck of cards (but not a perfect shuffle).

Links

Table of n, a(n) for n=1..17.

Formula

For n = 1..17 the values a(n) are achieved by the lexicographically least strings given below:

1 : 0

2 : 01

3 : 010

4 : 0110

5 : 00110

6 : 011001

7 : 0110001

8 : 01100110

9 : 011000110

10 : 0110001110

11 : 01110001110

12 : 011100001110

13 : 0111000001110

14 : 01100011110001

15 : 011000011110001

16 : 0111000011110001

17 : 01110000011110001

Example

For n = 3 one can obtain {010010, 001010, 010100, 001100} by self-shuffling 010, so a(3) = 4.

Prog

(Python) # uses a() in A191755; a(n)[2] generates the lex. least argmax
print([a(n)[1] for n in range(1, 9)]) # Michael S. Branicky, Sep 28 2021

Crossrefs

Cf. A191755.

Sequence in context: A362037 A368422 A283877 * A373808 A081490 A292478

Adjacent sequences: A331847 A331848 A331849 * A331851 A331852 A331853

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 29 2020

Extensions

a(11)-a(13) from Giovanni Resta, Jan 29 2020

a(14)-a(15) from Giovanni Resta, Jan 30 2020

a(16)-a(17) from Bert Dobbelaere, Feb 08 2020

Status

approved