A095830 Number of binary trees of path length n.

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

Offset

0,2

Comments

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n = 0..200 from Vincenzo Librandi)

G. Seroussi, On the number of t-ary trees with a given path length, arXiv:cs/0509046 [cs.DM], 2005-2007; 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.

Mathematica

terms = 44; B[_, _] = 0;
Do[B[w_, z_] = Series[z B[w, w z]^2 + 1, {w, 0, terms-1}, {z, 0, terms-1}] // Normal, {terms-1}];
CoefficientList[B[w, 1] - 1, w] (* Jean-François Alcover, Dec 03 2018 *)

Crossrefs

Cf. A106182.

Sequence in context: A090802 A375049 A129159 * A193915 A101621 A086484

Adjacent sequences: A095827 A095828 A095829 * A095831 A095832 A095833

Keyword

nonn

Author

Gadiel Seroussi (seroussi(AT)hpl.hp.com), Jul 10 2004

Status

approved