Binary Numbers Arranged

[Max]

Leroy Quet wrote:
> What is the sequence where the nth term, a(n), is the number of 
> permutations of (1,2,3,...,n) written in binary so that no adjacent 
> elements share a common 1-bit?
> 
> In other words, if b(m) and b(m+1) are adjacent elements written in 
> binary,
> then (b(m) AND b(m+1)) = 0 for 1 <= m <= n-1.
> (If a logical AND is applied to each pair of adjacent terms, the result 
> is zero.)
> 
> I get, as done by hand, the sequence:
> 1,2,0,4,2,0,0,0,0,20,...
> 
> If I did not make a mistake, and I very well could have, this sequence is 
> not yet in the EIS.
> 
> Could someone please calculate/submit the sequence if it is not yet in 
> the EIS?

I've got
1 2 0 4 2 0 0 0 8 32 0 8 0 0 0 0 0 64 0 1968

Let 2^k be the largest power of 2 less or equal n.
Note that element 2^k-1 can be adjacent only to 2^k. So 2^k-1 must be at the beginning or the end of the permutation while 2^k must be next to 2^k-1.
Each elements 2^k-1-2^i (i=1,...,k-1) can be adjacent only to 2^i, 2^k, and 2^k+2^i implying
that n must be >=2^k+2^(k-3) to yield a non-zero number of permutations.

> Additional sequences, which may or may not already be in the EIS:
> The first and last terms of the permutations must AND to zero as well.
> The permutations counted are of (0,1,2,...n), starting at 0 instead of at 
> 1.

This gives the same sequence if the permutations are counted up to rotations;
to count up with rotations simply multiple each term a(n) of the previous sequence by n+1.

Max