login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A138156 Sum of the path lengths of all binary trees with n edges. 4
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

a(n) = 2*A006419(n).

If (2*n+3) prime, then A138156(n) mod (2*n+3) == 0. - Alzhekeyev Ascar M, Jul 19 2011

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

Table of n, a(n) for n=0..22.

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.

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

Cf. A095830, A138157, A006419.

Sequence in context: A263218 A189305 A043011 * A280392 A192809 A198762

Adjacent sequences:  A138153 A138154 A138155 * A138157 A138158 A138159

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Mar 20 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 27 04:08 EDT 2017. Contains 284144 sequences.