cp's OEIS Frontend

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

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