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

Author

Emeric Deutsch

Keywords

• nonn

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

Crossrefs

Column k=1 of A102892.

Cf. A006013.

Programs

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

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

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