cp's OEIS Frontend

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.

%I A109468 #19 Aug 19 2022 10:38:31
%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,0,0,0,0,0,
%T A109468 0,0,0,0,0,0,1024,0,0,0
%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.
%C A109468 Let 2^k be the smallest power of 2 that is greater than n. Note that for 0 <= i <= k-1, the element 2^k-1-2^i can only be adjacent to 2^i, so it must be at the beginning or the end of the permutation. If n >= 2^k-1-2^(k-3) and k >= 3, there are at least three such elements <= n, which is impossible, so a(n) = 0. Together with the preceding comment, this means that a(n) = 0 when 2^k-2^(k-3)-1 <= n <= 2^k+2^(k-3)-1, k >= 3, i.e., when n is in one of the intervals 6-8, 13-17, 27-35, 55-71, ... . - _Pontus von Brömssen_, Aug 15 2022
%K A109468 nonn,more
%O A109468 1,2
%A A109468 _N. J. A. Sloane_, based on a suggestion from _Leroy Quet_, Aug 21 2005
%E A109468 More terms from _Max Alekseyev_, Aug 28 2005
%E A109468 a(26)-a(35) from _Pontus von Brömssen_, Aug 15 2022
%E A109468 a(36)-a(40) from _Max Alekseyev_, Aug 17 2022