A062236 Sum of the levels of all nodes in all noncrossing trees with n edges.

1, 8, 58, 408, 2831, 19496, 133638, 913200, 6226591, 42387168, 288194424, 1957583712, 13286865060, 90126841064, 611029568078, 4140789069408, 28050809681679, 189964288098632, 1286119453570746, 8705397371980728

Offset

1,2

Links

Harry J. Smith, Table of n, a(n) for n=1..200

Emeric Deutsch and M. Noy, New statistics on non-crossing trees, in: Formal Power Series and Algebraic Combinatorics (Proceedings of the 12th International Conference, FPSAC'00, Moscow, Russia, 2000), pp. 667-676, Springer, Berlin, 2000.

Emeric Deutsch and M. Noy, Statistics on non-crossing trees, Discrete Math., 254 (2002), 75-87 (see Th. 6). [From N. J. A. Sloane, Dec 17 2012]

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

Formula

G.f.: g*(g-1)/(3-2*g)^2, where function g=g(x) satisfies g=1+xg^3, and can be expressed as g(x) = 2*sin(arcsin(3*sqrt(3*x)/2)/3)/sqrt(3*x). [Corrected by Max Alekseyev, Oct 27 2022]

g(x) = Sum_{n >= 0} binomial(3*n,n) / (2*n+1) * x^n. - Max Alekseyev, Oct 27 2022

Recurrence: 8*n*(2*n-1)*a(n) = 6*(36*n^2-45*n+10)*a(n-1) - 81*(3*n-5)*(3*n-1)*a(n-2). - Vaclav Kotesovec, Oct 13 2012

a(n) ~ 3^(3*n)/2^(2*n+2). - Vaclav Kotesovec, Oct 13 2012

a(n) = Sum_{i=0..n-1} C(3*i-1,i)*C(3*(n-i),n-i-1). - Vladimir Kruchinin, Jun 09 2020

a(n) = 2^(n-2)*(3*n-1)*hypergeometric([-3*n, 1-n, -n+4/3], [-n, -n+1/3], -1/2). The a(n) are values of the polynomials A358091. - Peter Luschny, Oct 28 2022

Maple

a := n -> add(2^(n-2-i)*(n-i)*(3*n-3*i-1)*binomial(3*n, i), i=0..n-1)/n;
A062236 := n -> 2^(n-2)*(3*n-1)*hypergeom([-3*n, 1-n, -n+4/3], [-n, -n+1/3], -1/2):
seq(simplify(A062236(n)), n = 1..29); # Peter Luschny, Oct 28 2022

Mathematica

Table[Sum[2^(n-2-k)*(n-k)*(3*n-3*k-1)*Binomial[3*n, k], {k, 0, n-1}]/n, {n, 1, 20}] (* Vaclav Kotesovec, Oct 13 2012 *)

Prog

(PARI) { for (n=1, 200, a=sum(i=0, n-1, 2^(n-2-i)*(n-i)*(3*n-3*i-1)*binomial(3*n, i))/n; write("b062236.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 03 2009

Crossrefs

Cf. A001764, A358091.

Sequence in context: A162272 A273584 A037532 * A178730 A190978 A254663

Adjacent sequences: A062233 A062234 A062235 * A062237 A062238 A062239

Keyword

nonn

Author

Emeric Deutsch, Jun 30 2001

Status

approved