A073663 - OEIS

%I #21 Sep 08 2022 08:45:06

%S 1,2,8,30,113,428,1629,6226,23881,91884,354484,1370812,5312058,

%T 20622904,80196055,312319530,1217938665,4755296460,18586968840,

%U 72723903780,284804791230,1116315593640,4378929921210,17189573707956

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

%H G. C. Greubel, <a href="/A073663/b073663.txt">Table of n, a(n) for n = 0..1000</a>

%H J. Riordan, <a href="http://dx.doi.org/10.1016/S0097-3165(75)80010-0">Enumeration of plane trees by branches and endpoints</a>, J. Comb. Theory (A) 19, 1975, 214-222.

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

%F 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).

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

%F 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

%e 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.

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

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

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

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

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

%Y First differences of A076540.

%K nonn

%O 0,2

%A _Emeric Deutsch_, Sep 01 2002