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

Author

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

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

Cf. A106182.

Programs

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 *)

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.