A073663 Total number of branches of length k (k>=1) in all ordered trees with n+k edges (it is independent of k).

1, 2, 8, 30, 113, 428, 1629, 6226, 23881, 91884, 354484, 1370812, 5312058, 20622904, 80196055, 312319530, 1217938665, 4755296460, 18586968840, 72723903780, 284804791230, 1116315593640, 4378929921210, 17189573707956

Offset: 0

Author

Emeric Deutsch, Sep 01 2002

Keywords

• nonn

Examples

			a(2)=8 because for n=2 and k=1 (for example), the five ordered trees with n+k=3 edges have altogether 0+3+1+1+3=8 branches of length 1.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• J. Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214-222.

Crossrefs

First differences of A076540.

Programs

GAP

Concatenation([1], List([1..30], n-> 3*(3*n^3+2*n^2+n-2)* Binomial(2*n, n)/(2*(n+1)*(n+2)*(2*n-1)))); # G. C. Greubel, Jul 22 2019

Magma

[1] cat [3*(3*n^3+2*n^2+n-2)*Catalan(n)/(2*(n+2)*(2*n-1)): n in [1..30]]; // G. C. Greubel, Jul 22 2019

Mathematica

Table[If[n==0, 1, 3*(3*n^3+2*n^2+n-2)*CatalanNumber[n]/(2*(n+2)*(2*n - 1))], {n,0,30}] (* G. C. Greubel, Jul 22 2019 *)

PARI

vector(30, n, n--; if(n==0, 1, 3*(3*n^3+2*n^2+n-2)*binomial(2*n, n)/(2*(n+1)*(n+2)*(2*n-1)))) \\ G. C. Greubel, Jul 22 2019

Sage

[1]+[3*(3*n^3+2*n^2+n-2)*catalan_number(n)/(2*(n+2)*(2*n-1)) for n in (1..30)] # G. C. Greubel, Jul 22 2019

Formula

a(n) = binomial(2n+2, n) - 2*binomial(2n, n-1) + binomial(2n-2, n-2) (n > 0).

a(n) = 3*(3*n^3 + 2*n^2 + n - 2)*binomial(2*n, n)/(2*(n+1)*(n+2)*(2*n-1)) (n > 0).

G.f.: (1-z)^2*C^2/sqrt(1-4z), where C = (1-sqrt(1-4z))/(2z) is the Catalan function.

D-finite with recurrence (n+2)*a(n) +(-7*n-5)*a(n-1) +2*(7*n-8)*a(n-2) +4*(-2*n+7)*a(n-3)=0. - R. J. Mathar, Jul 26 2022