Permutations, Adjacents Have Near-by Binary 1's

[Max]

Leroy Quet wrote:
>>
>> Take the integers 1 through n written in binary.
>> The nth term of the sequence is the number of permutations of these 
>> binary numbers such that every 1-digit in the kth element (2<=k<=n) of 
>> the permutation is either in the same position as, is one position to 
>> the left of, or is one position to the right of a 1-digit in the 
>> (k-1)th element written in binary.
> 
> [...]
> 
>> I get that the sequence of number of such permutations for 1 through n
>> begins 1, 2, 6, 8,...

Max wrote:
>
> I've got
> 1 2 6 8 24 168 840 1008 4032 32160 192960 1297440 9082080 126846720 
> 1141620480 1243468800 4490307360 53812332000 526257365760 3736568586240
> 
> and respectively the number of circular permutations of this kind (up to 
> rotations):
> 1 1 2 1 2 18 72 42 126 1080 5400 42240 253440 3578400 28627200 16914240 
> 54396720 620978400 5417102880 40328285760


I have submitted these as A115506 and A115507 as well as
two more sequences A115508 and A115509 that require the same condition fulfilled in two directions, i.e.,


%S A115508  1 2 6 4 4 40 120 72 140 824 3312 22320 110976 1369536 9477120 3596160 3235584 36927360 286846848 700001376
%N A115508 The number of permutations where for every pair of adjacent elements one element in binary notation has ones at the same or adjacent positions to those of the other element.


%S A115509  1 1 2 0 0 2 4 0 0 0 0 432 1968 24960 161280 0 0 0 0 0 0
%N A115509 The number of circular permutations where for every pair of adjacent elements one element in binary notation has ones at the same or adjacent positions to those of the other element.
%C A115509 Conjecture: if 2^(k+1)<=n<3*2^k for k>=1, then a(n)=0.


Max