|
Search: id:A138156
|
|
|
| A138156 |
|
Sum of the path lengths of all binary trees with n edges. |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
a(n)=2*A006419(n).
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1997, Vol. 1, p. 405 (exercise 5) and p. 595 (solution).
|
|
FORMULA
|
a(n)=4^(n+1) - (3n+4)binom(2n+2,n+1)/(n+2). G.f.=1/[z*sqrt(1-4z)] - [(1-z)/sqrt(1-4z)-1]/z^2.
|
|
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:=proc(n) options operator, arrow: 4^(n+1)-(3*n+4)*binomial(2*n+2, n+1)/(n+2) end proc: seq(a(n), n=0..22);
|
|
CROSSREFS
|
Cf. A095830, A138157, A006419.
Adjacent sequences: A138153 A138154 A138155 this_sequence A138157 A138158 A138159
Sequence in context: A002058 A095933 A043011 this_sequence A119913 A104871 A034573
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 20 2008
|
|
|
Search completed in 0.002 seconds
|
