login
The OEIS is supported by the many generous donors 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. 7
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
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
a(n) is the number of parking functions of size n avoiding the patterns 213, 312, and 321. - Lara Pudwell, Apr 10 2023
LINKS
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combinat. Theory, Ser A, 19, 214-222, 1975.
Lin Yang and Shengliang Yang, Protected Branches in Ordered Trees, J. Math. Study (2023) Vol. 56, No. 1, 1-17.
FORMULA
a(n) = (3*n^2-2*n+1)*binomial(2*n, n)/(2*(n+1)*(2*n-1)).
G.f.: (1-z)*(C-1)/sqrt(1-4*z), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function.
a(n) = binomial(2n-1, n-2) + binomial(2n-2, n-1). - David Callan, Nov 06 2003
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
D-finite with recurrence (n+1)*a(n) +(-7*n+1)*a(n-1) +2*(7*n-12)*a(n-2) +4*(-2*n+7)*a(n-3)=0. - R. J. Mathar, Jul 26 2022
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.
Sequence in context: A079935 A281593 A113437 * A196472 A258471 A176085
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:53 EDT 2024. Contains 370953 sequences. (Running on oeis4.)