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
KEYWORD
nonn
AUTHOR
Mike Stay, Aug 13 2011
STATUS
approved