|
Search: id:A109468
|
|
|
| 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. |
|
+0
1
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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.)
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.
|
|
CROSSREFS
|
Adjacent sequences: A109465 A109466 A109467 this_sequence A109469 A109470 A109471
Sequence in context: A079124 A056737 A008797 this_sequence A081880 A037035 A112824
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
njas, based on a suggestion from Leroy Quet, Aug 21 2005
|
|
EXTENSIONS
|
More terms from Max Alekseyev (maxal(AT)cs.ucsd.edu), Aug 28 2005
|
|
|
Search completed in 0.002 seconds
|
