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,2

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.

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

Example

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.

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 *)

Prog

(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
(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
(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
(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

Crossrefs

First differences of A076540.

Sequence in context: A274798 A281949 A162551 * A266319 A155116 A133915

Adjacent sequences: A073660 A073661 A073662 * A073664 A073665 A073666

Keyword

nonn

Author

Emeric Deutsch, Sep 01 2002

Status

approved