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, 58912358137385559, 398607288093924192, 2696583955707785256
Offset: 1
Keywords
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.
Programs
-
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 *) -
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
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
From Seiichi Manyama, Jul 26 2025: (Start)
G.f.: g/(1-3*g)^2 where g*(1-g)^2 = x.
L.g.f.: Sum_{k>=1} a(k)*x^k/k = (1/2) * log( Sum_{k>=0} binomial(3*k-1,k)*x^k ). (End)
From Seiichi Manyama, Jul 29 2025: (Start)
a(n) = Sum_{k=0..n-1} binomial(3*k-1+l,k) * binomial(3*n-3*k-l,n-k-1) for every real number l. This is a generalization of a formula by Vladimir Kruchinin, Jun 09 2020.
a(n) = Sum_{k=0..n-1} 2^(n-k-1) * binomial(3*n,k).
a(n) = Sum_{k=0..n-1} 3^(n-k-1) * binomial(2*n+k,k). (End)