A076540 Number of branches in all ordered trees with n edges.

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

Offset: 1

Author

Emeric Deutsch, Oct 18 2002

Keywords

• nonn
• easy

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

Examples

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

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..1664
• 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.

Crossrefs

First differences of A001791. First differences are in A073663.

Cf. A136535, A005717.

Programs

Magma

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

Mathematica

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

PARI

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

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