A030983 Number of rooted noncrossing trees with n nodes such that root has degree 1 and the child of the root has degree at least 2.

0, 3, 16, 83, 442, 2420, 13566, 77539, 450340, 2650635, 15777450, 94815732, 574518536, 3506232184, 21533144486, 132980242755, 825304177544, 5144743785545, 32199189658020, 202252227085755, 1274578959894450, 8056409137803600, 51063344718826440

Offset

3,2

Comments

From Andrei Asinowski, May 09 2020: (Start)

With offset 0 (i.e., a(0) = 0 and a(1) = 3), a(n) is the total number of down-steps after the final up-step in all 2_1-Dyck paths of length 3*n.

A 2_1-Dyck path is a lattice path with steps U = (1, 2) and d = (1, -1) that starts at (0,0), stays (weakly) above the line y = -1, and ends at the x-axis.

For n = 2, a(2) = 16 is the total number of down-steps after the final up-step in dUddUd, dUdUdd, dUUddd, UdddUd, UddUdd, UdUddd, UUdddd (thus, 1 + 2 + 3 + 1 + 2 + 3 + 4). (End)

Links

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

A. Asinowski, B. Hackl, and S. Selkirk, Down step statistics in generalized Dyck paths, arXiv:2007.15562 [math.CO], 2020.

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

Index entries for sequences related to rooted trees

Formula

a(n) = (19*n - 31)*binomial(3*n - 8, n - 4)/(n - 1)/(2*n - 3).

G.f.: g^3*(3 - 2*g) where g*(1 - g)^2 = x. - Mark van Hoeij, Nov 09 2011 [That is, g = (4/3) * sin((1/3)*arcsin(sqrt(27*x/4)))^2 = x*(o.g.f. of A006013). - Petros Hadjicostas, Aug 08 2020]

From Vladimir Kruchinin, Mar 06 2013: (Start)

a(n) = binomial(3*n-5, 2*n-3)/(n-1) - 2*binomial(3*n-8, 2*n-5)/(n-2), n > 2.

a(n) = Sum_{i=1..n-3} binomial(3*i-2, 2*i-1) * binomial(3*(n-i-2), 2*(n-i-2)-1)/ (i*(n-i-2)). (End)

a(n) ~ (76*3^(3*n - 15/2))/(4^n*sqrt(Pi)*n^(3/2)). - Peter Luschny, Aug 08 2020

D-finite with recurrence 2*(n-1)*(2*n-3)*a(n) +(-43*n^2+196*n-213)*a(n-1) +2*(62*n^2-446*n+759)*a(n-2) -12*(3*n-14)*(3*n-16)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

D-finite with recurrence 2*(n-1)*(n-4)*(2*n-3)*(19*n-50)*a(n) -3*(3*n-10)*(3*n-8)*(n-3)*(19*n-31)*a(n-1)=0. - R. J. Mathar, Jul 26 2022

Maple

h := arcsin((3*sqrt(3)*sqrt(x))/2)/3:
gf := x*(64/9)*sin(h)^6*(1 - sin(h)^2*(8/9)): ser := series(gf, x, 32):
seq(coeff(ser, x, n), n=3..25); # Peter Luschny, Aug 08 2020
# Recurrence:
a := proc(n) option remember; if n < 4 then return 0 fi; if n = 4 then return 3 fi;
-((378*n^3 - 4536*n^2 + 18102*n - 24024)*a(n - 2) + (-1271*n^3 + 10308*n^2 - 26857*n + 22020)*a(n - 1))/(180*n^3 - 1170*n^2 + 2070*n - 1080) end:
seq(a(n), n=3..25); # Peter Luschny, Aug 08 2020

Mathematica

a[n_] := Binomial[3n-5, n-2]/(n-1) - 2 Binomial[3n-8, n-3]/(n-2);
a /@ Range[3, 25] (* Jean-François Alcover, Nov 03 2020, after A102892 *)

Prog

(PARI) a(n)=(19*n-31)*binomial(3*n-8, n-4)/(n-1)/(2*n-3); /* Joerg Arndt, Mar 07 2013 */
(PARI) concat(0, Vec((g->g^3*(3-2*g))(serreverse(x-2*x^2+x^3 + O(x^25))))) \\ Andrew Howroyd, Nov 12 2017

Crossrefs

Column k=1 of A102892.

Cf. A006013.

Sequence in context: A164100 A041707 A037584 * A069429 A275402 A026131

Adjacent sequences: A030980 A030981 A030982 * A030984 A030985 A030986

Keyword

nonn

Author

Emeric Deutsch

Status

approved