|
|
A138156
|
|
Sum of the path lengths of all binary trees with n edges.
|
|
5
|
|
|
0, 2, 14, 74, 352, 1588, 6946, 29786, 126008, 527900, 2195580, 9080772, 37392864, 153434536, 627778954, 2562441466, 10438340104, 42449348236, 172376641924, 699100282156, 2832205421824, 11462854280536, 46354571222164
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1997, Vol. 1, p. 405 (exercise 5) and p. 595 (solution).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 4^(n+1) - (3*n+4) * C(2*n+2,n+1)/(n+2).
G.f.: 1/(z*(1-4*z)) - ((1-z)/sqrt(1-4*z)-1)/z^2.
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
|
|
EXAMPLE
|
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.
|
|
MAPLE
|
a:= n-> 4^(n+1)-(3*n+4)*binomial(2*n+2, n+1)/(n+2): seq(a(n), n=0..22);
|
|
MATHEMATICA
|
Table[4^(n+1)-(3n+4) Binomial[2n+2, n+1]/(n+2), {n, 0, 30}] (* Harvey P. Dale, Dec 14 2014 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|