%I A109468
%S A109468 1,2,0,4,2,0,0,0,8,32,0,8,0,0,0,0,0,64,0,1968,508,0,0,0,16
%N A109468 a(n) is the number of permutations of (1,2,3,...,n) written in binary 
               such that no adjacent elements share a common 1-bit.
%C A109468 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.)
%C A109468 Let 2^k be the largest power of 2 <= 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. The 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 nonzero number of 
               permutations.
%H A109468 Leroy Quet, <a href="http://www.prism-of-spirals.net/">Home Page</a> 
               (listed in lieu of email address)
%Y A109468 Sequence in context: A079124 A056737 A008797 this_sequence A081880 A144289 
               A037035
%Y A109468 Adjacent sequences: A109465 A109466 A109467 this_sequence A109469 A109470 
               A109471
%K A109468 nonn
%O A109468 1,2
%A A109468 N. J. A. Sloane (njas(AT)research.att.com), based on a suggestion from 
               Leroy Quet, Aug 21 2005
%E A109468 More terms from Max Alekseyev (maxale(AT)gmail.com), Aug 28 2005