cp's OEIS Frontend

A138156 Sum of the path lengths of all binary trees with n edges.

%I A138156 #24 Jul 06 2023 01:56:56
%S A138156 0,2,14,74,352,1588,6946,29786,126008,527900,2195580,9080772,37392864,
%T A138156 153434536,627778954,2562441466,10438340104,42449348236,172376641924,
%U A138156 699100282156,2832205421824,11462854280536,46354571222164
%N A138156 Sum of the path lengths of all binary trees with n edges.
%C A138156 a(n) = 2*A006419(n).
%C A138156 If (2*n+3) prime, then A138156(n) mod (2*n+3) == 0. - _Alzhekeyev Ascar M_, Jul 19 2011
%D A138156 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1997, Vol. 1, p. 405 (exercise 5) and p. 595 (solution).
%H A138156 Michael De Vlieger, <a href="/A138156/b138156.txt">Table of n, a(n) for n = 0..1659</a>
%H A138156 Jean-Luc Baril and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/pathwall.pdf">Fibonacci and Catalan paths in a wall</a>, 2023.
%F A138156 a(n) = 4^(n+1) - (3*n+4) * C(2*n+2,n+1)/(n+2).
%F A138156 G.f.: 1/(z*(1-4*z)) - ((1-z)/sqrt(1-4*z)-1)/z^2.
%F A138156 D-finite with recurrence (n+2)*a(n) +(-9*n-10)*a(n-1) +2*(12*n+1)*a(n-2) +8*(-2*n+3)*a(n-3)=0. - _R. J. Mathar_, Jul 26 2022
%e A138156 a(1) = 2 because the trees with one edge are (i) root with a left child and (ii) root with a right child, each having path length 1.
%p A138156 a:= n-> 4^(n+1)-(3*n+4)*binomial(2*n+2, n+1)/(n+2): seq(a(n), n=0..22);
%t A138156 Table[4^(n+1)-(3n+4) Binomial[2n+2,n+1]/(n+2),{n,0,30}] (* _Harvey P. Dale_, Dec 14 2014 *)
%Y A138156 Cf. A095830, A138157, A006419.
%K A138156 nonn
%O A138156 0,2
%A A138156 _Emeric Deutsch_, Mar 20 2008