Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #24 Jul 06 2023 01:56:56
%S 0,2,14,74,352,1588,6946,29786,126008,527900,2195580,9080772,37392864,
%T 153434536,627778954,2562441466,10438340104,42449348236,172376641924,
%U 699100282156,2832205421824,11462854280536,46354571222164
%N Sum of the path lengths of all binary trees with n edges.
%C a(n) = 2*A006419(n).
%C If (2*n+3) prime, then A138156(n) mod (2*n+3) == 0. - _Alzhekeyev Ascar M_, Jul 19 2011
%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1997, Vol. 1, p. 405 (exercise 5) and p. 595 (solution).
%H Michael De Vlieger, <a href="/A138156/b138156.txt">Table of n, a(n) for n = 0..1659</a>
%H 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 a(n) = 4^(n+1) - (3*n+4) * C(2*n+2,n+1)/(n+2).
%F G.f.: 1/(z*(1-4*z)) - ((1-z)/sqrt(1-4*z)-1)/z^2.
%F 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 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 a:= n-> 4^(n+1)-(3*n+4)*binomial(2*n+2, n+1)/(n+2): seq(a(n), n=0..22);
%t Table[4^(n+1)-(3n+4) Binomial[2n+2,n+1]/(n+2),{n,0,30}] (* _Harvey P. Dale_, Dec 14 2014 *)
%Y Cf. A095830, A138157, A006419.
%K nonn
%O 0,2
%A _Emeric Deutsch_, Mar 20 2008