login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
0, 3, 16, 83, 442, 2420, 13566, 77539, 450340, 2650635, 15777450, 94815732, 574518536, 3506232184, 21533144486, 132980242755, 825304177544, 5144743785545, 32199189658020, 202252227085755, 1274578959894450, 8056409137803600, 51063344718826440 (list; graph; refs; listen; history; text; internal format)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 07:50 EDT 2021. Contains 348074 sequences. (Running on oeis4.)