A102594 Number of noncrossing trees with n edges in which no border edges emanate from the root.

1, 0, 0, 1, 7, 42, 245, 1428, 8379, 49588, 296010, 1781325, 10798788, 65900296, 404565252, 2496994136, 15486165555, 96464124648, 603262881620, 3786268349115, 23842082904255, 150586208376450, 953736669989985

Offset

0,5

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

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

Emanuele Munarini, Shifting Property for Riordan, Sheffer and Connection Constants Matrices, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.2.

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

Formula

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

G.f.: g*(1+z-2*z*g), where g = 1+z*g^3 is the g.f. of the ternary numbers (A001764).

From Karol A. Penson, Mar 12 2018: (Start)

a(n+3) = 7*binomial(3*n+6, 2*n+6)/(2*n+7).

a(n+3) is the n-th moment of a signed function v(x) on (0,27/4), i.e., in Maple notation, a(n+3) = int(x^n*v(x) , x = 0..27/4), n = 0,1..., where v(x) = -sqrt(3)*x^(4/3)*(7*x^(1/3)*hypergeom([-5/6, -1/3, 8/3], [2/3, 4/3], 4*x/27))-3*hypergeom([-7/6, -2/3, 7/3], [1/3, 2/3], 4*x/27)))/(6*Pi). The function v(x) vanishes at x = 0 and x = 27/4. In addition it has one zero in the interval between x = 0 and x = 27/4. (End)

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

Example

a(2)=0 because in all the three noncrossing trees with 2 edges, namely, /_, /\ and _\, the root (=the top vertex) is incident with at least one border edge.

Maple

a:=n->7/3*(n-1)*(n-2)*binomial(3*n, n)/(3*n-1)/(2*n+1)/(3*n-2): 1, seq(a(n), n=1..25);

Mathematica

a[0] = a[3] = 1; a[n_] := 7*Binomial[3n-3, 2n+1]/(n-3); Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Jan 21 2013 *)

Prog

(PARI) a(n) = if (n==0, 1, 7/3*(n-1)*(n-2)*binomial(3*n, n)/(3*n-1)/(2*n+1)/(3*n-2)); \\ Michel Marcus, Oct 26 2015
(PARI) Vec((g->g*(1+x-2*x*g))(1+serreverse(x/(1+x)^3 + O(x^30)))) \\ Andrew Howroyd, Nov 17 2017

Crossrefs

Column k=0 of A102593.

Cf. A001764.

Sequence in context: A050152 A030240 A054890 * A053142 A214941 A162941

Adjacent sequences: A102591 A102592 A102593 * A102595 A102596 A102597

Keyword

nonn

Author

Emeric Deutsch, Jan 22 2005

Status

approved