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

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

Author

John W. Layman, Jul 14 2011

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A191755, A192296.