cp's OEIS Frontend

A095830 Number of binary trees of path length n.

%I A095830 #17 Jan 31 2019 21:30:32
%S A095830 1,2,1,4,4,2,14,8,12,28,21,52,52,72,92,160,212,178,446,360,628,920,
%T A095830 918,1568,1784,2676,2960,4724,5360,7280,10876,10936,17484,21732,28469,
%U A095830 34224,48648,61232,78196,105680,120904,178848,217404,279312
%N A095830 Number of binary trees of path length n.
%C A095830 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.
%H A095830 Alois P. Heinz, <a href="/A095830/b095830.txt">Table of n, a(n) for n = 0..1000</a> (terms n = 0..200 from Vincenzo Librandi)
%H A095830 G. Seroussi, <a href="https://arxiv.org/abs/cs/0509046">On the number of t-ary trees with a given path length</a>, arXiv:cs/0509046 [cs.DM], 2005-2007; Algorithmica 46(3), 557-565, 2006.
%F A095830 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.
%e A095830 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.
%e A095830 a(2) = 1 because there is just one binary tree of path length 2: a root with its two children.
%t A095830 terms = 44; B[_, _] = 0;
%t A095830 Do[B[w_, z_] = Series[z B[w, w z]^2 + 1, {w, 0, terms-1}, {z, 0, terms-1}] // Normal, {terms-1}];
%t A095830 CoefficientList[B[w, 1] - 1, w] (* _Jean-François Alcover_, Dec 03 2018 *)
%Y A095830 Cf. A106182.
%K A095830 nonn
%O A095830 0,2
%A A095830 Gadiel Seroussi (seroussi(AT)hpl.hp.com), Jul 10 2004