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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A076540 Number of branches in all ordered trees with n edges. 5
1, 3, 11, 41, 154, 582, 2211, 8437, 32318, 124202, 478686, 1849498, 7161556, 27784460, 107980515, 420300045, 1638238710, 6393535170, 24980504010, 97704407790, 382509199020, 1498824792660, 5877754713870, 23067328421826, 90590960500524, 356002519839652 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Binomial[2n-1,n-2]+binomial[2n-2,n-1]. - David Callan, Nov 06 2003

Row sums of triangle A136535. - Gary W. Adamson, Jan 04 2008

The average of the n terms a(1),...,a(n) is C(n) = A000108(n), the n-th Catalan number. - Franklin T. Adams-Watters, May 20 2010

Binomial transform of A005717. - Peter Luschny, Jan 17 2012

LINKS

Table of n, a(n) for n=1..26.

J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combinat. Theory, Ser A, 19, 214-222, 1975.

FORMULA

a(n)=(3n^2-2n+1)binom(2n, n)/[2(n+1)(2n-1)]; g.f.=(1-z)(C-1)/sqrt(1-4z), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

a(n+1) = [x^n](1 + x + x^2)*(1 + x)^(2*n) = binomial(2*n,n) + binomial(2*n,n-1) + binomial(2*n,n-2). - Peter Bala, Jun 15 2015

EXAMPLE

a(3)=11 because the five ordered trees with 3 edges have 1+3+2+2+3=11 branches altogether.

MATHEMATICA

Table[Binomial[2 n, n] + Binomial[2 n, n-1] + Binomial[2 n, n-2], {n, 0, 30}] (* Vincenzo Librandi, Jun 17 2015 *)

PROG

(PARI) vector(30, n, binomial(2*n-1, n-2)+binomial(2*n-2, n-1)) \\ Michel Marcus, Jun 17 2015

(MAGMA) [Binomial(2*n, n)+Binomial(2*n, n-1)+Binomial(2*n, n-2): n in [0..30]]; // Vincenzo Librandi, Jun 17 2015

CROSSREFS

First differences of A001791. First differences are in A073663.

Cf. A136535, A005717.

Sequence in context: A079935 A281593 A113437 * A196472 A258471 A176085

Adjacent sequences:  A076537 A076538 A076539 * A076541 A076542 A076543

KEYWORD

nonn,easy

AUTHOR

Emeric Deutsch, Oct 18 2002

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 February 18 03:43 EST 2018. Contains 299298 sequences. (Running on oeis4.)