A194045 - OEIS

%I #11 Jun 23 2022 20:30:15

%S 0,4,20,24,84,88,100,104,112,340,344,356,360,368,404,408,420,424,432,

%T 452,456,464,480,1364,1368,1380,1384,1392,1428,1432,1444,1448,1456,

%U 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

%N Numbers whose binary expansion is a preorder traversal of a binary tree

%C 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.

%F a(n) = 4 * A057520(n). [_Joerg Arndt_, Sep 22 2012]

%F a(0)=0, a(n) = 2 * A014486(n) for n>=1. [_Joerg Arndt_, Sep 22 2012]

%o (JavaScript)

%o // n is the number of internal nodes (or 1s in the binary expansion)

%o // f is a function to display each result

%o function trees(n, f) {

%o   // h is the "height", thinking of 1 as a step up and 0 as a step down

%o   // s is the current state

%o   function enumerate(n, h, s, f) {

%o     if (n===0 && h===0) { f(2 * s); }

%o     else {

%o       if (h > 0) { enumerate(n, h - 1, 2 * s, f) }

%o       if (n > 0) { enumerate(n - 1, h + 1, 2 * s + 1, f) }

%o     }

%o   }

%o   enumerate(n, 0, 0, f);

%o }

%Y Cf. A000108.

%K nonn

%O 0,2

%A _Mike Stay_, Aug 13 2011