|
|
A193020
|
|
Number of distinct self-shuffles of the word given by the binary representation of n.
|
|
6
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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.
|
|
LINKS
|
|
|
EXAMPLE
|
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.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|