login
A194045
Numbers whose binary expansion is a preorder traversal of a binary tree
0
0, 4, 20, 24, 84, 88, 100, 104, 112, 340, 344, 356, 360, 368, 404, 408, 420, 424, 432, 452, 456, 464, 480, 1364, 1368, 1380, 1384, 1392, 1428, 1432, 1444, 1448, 1456, 1476, 1480, 1488, 1504, 1620, 1624, 1636, 1640, 1648, 1684, 1688, 1700, 1704, 1712, 1732, 1736, 1744, 1760, 1812, 1816, 1828, 1832, 1840, 1860, 1864, 1872, 1888, 1924, 1928, 1936, 1952, 1984
OFFSET
0,2
COMMENTS
When traversing the tree in preorder, emit 1 at each node and 0 if it has no child on the current branch. The smallest binary tree is empty, so we emit 0 at the root; thus a(0) = 0. The next binary tree is a single node (emit 1) with no left (emit 0) or right child (emit 0); thus a(1) = 100 in binary or 4.
FORMULA
a(n) = 4 * A057520(n). [Joerg Arndt, Sep 22 2012]
a(0)=0, a(n) = 2 * A014486(n) for n>=1. [Joerg Arndt, Sep 22 2012]
PROG
(JavaScript)
// n is the number of internal nodes (or 1s in the binary expansion)
// f is a function to display each result
function trees(n, f) {
// h is the "height", thinking of 1 as a step up and 0 as a step down
// s is the current state
function enumerate(n, h, s, f) {
if (n===0 && h===0) { f(2 * s); }
else {
if (h > 0) { enumerate(n, h - 1, 2 * s, f) }
if (n > 0) { enumerate(n - 1, h + 1, 2 * s + 1, f) }
}
}
enumerate(n, 0, 0, f);
}
CROSSREFS
Cf. A000108.
Sequence in context: A298040 A174134 A032425 * A097251 A202070 A198831
KEYWORD
nonn
AUTHOR
Mike Stay, Aug 13 2011
STATUS
approved