|
Search: id:A095830
|
|
|
| A095830 |
|
Number of binary trees of path length n. |
|
+0
6
|
|
| 1, 2, 1, 4, 4, 2, 14, 8, 12, 28, 21, 52, 52, 72, 92, 160, 212, 178, 446, 360, 628, 920, 918, 1568, 1784, 2676, 2960, 4724, 5360, 7280, 10876, 10936, 17484, 21732, 28469, 34224, 48648, 61232, 78196, 105680, 120904, 178848, 217404, 279312
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
The cited preprint gives an asymptotic estimate for the number of trees as the path length goes to infinity, for t-ary trees, t >= 2. This sequence corresponds to t=2.
|
|
LINKS
|
G. Seroussi, On the number of t-ary trees with a given path length, Algorithmica 46(3), 557-565, 2006.
|
|
FORMULA
|
G.f. = B(w, 1) - 1, where B(w, z) satisfies the functional equation B(w, z) = z B(w, wz)^2 + 1. B(w, z) is the g.f. for the number of binary trees of given path length and number of nodes (see Knuth Vol. 1 Sec. 2.3.4.5); B(1, z) is the g.f. for the Catalan numbers; for B(w, w) see A108643.
|
|
EXAMPLE
|
a(1) = 2 because there are two binary trees of path length 1: a root with a left child and a root with a right child.
a(2) = 1 because there is just one binary tree of path length 2: a root with its two children.
|
|
CROSSREFS
|
Cf. A106182.
Sequence in context: A051289 A090802 A129159 this_sequence A101621 A086484 A091335
Adjacent sequences: A095827 A095828 A095829 this_sequence A095831 A095832 A095833
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Gadiel Seroussi (seroussi(AT)hpl.hp.com), Jul 10 2004
|
|
|
Search completed in 0.002 seconds
|
