%I #13 Apr 26 2013 22:15:17
%S 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,
%T 8,5,1,6,25,32,40,27,40,54,30,19,40,32,27,37,36,32,10,15,40,37,36,24,
%U 27,27,12,20,30,19,12,15,10,6,1,7,36,50,75,48,77,120
%N Number of distinct self-shuffles of the word given by the binary representation of n.
%C See _Jeffrey Shallit_'s A191755 for the definition of self-shuffle and a link to a preprint of the paper "Shuffling and Unshuffling".
%C 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.
%H Alois P. Heinz, <a href="/A193020/b193020.txt">Table of n, a(n) for n = 0..2048</a>
%e 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.
%Y Cf. A191755, A192296.
%K nonn
%O 0,3
%A _John W. Layman_, Jul 14 2011