A102892 -id:A102892 - cp's OEIS frontend

A102893 Number of noncrossing trees with n edges and having degree of the root at least 2.

1, 0, 1, 5, 25, 130, 700, 3876, 21945, 126500, 740025, 4382625, 26225628, 158331880, 963250600, 5899491640, 36345082425, 225082957512, 1400431689475, 8749779798375, 54874635255825, 345329274848250, 2179969531405680

Offset: 0

Emeric Deutsch, Jan 16 2005

[a(n+2)]= [1,5,25,130,700,...] is the self-convolution 5th power of A001764. - Philippe Deléham, Nov 11 2009

a(n) is the number of dissections of a convex (2n+2)-sided polygon by nonintersecting diagonals into quadrilaterals such that at least one of the dividing diagonals passes through a chosen vertex. - Muhammed Sefa Saydam, Jan 24 2025

			a(2)=1 because among the noncrossing trees with 2 edges, namely /_, _\ and /\, only the last one has root degree >1.

Andrew Howroyd, Table of n, a(n) for n = 0..200
David Bevan, Robert Brignall, Andrew Elvey Price and Jay Pantone, A structural characterisation of Av(1324) and new bounds on its growth rate, arXiv preprint arXiv:1711.10325 [math.CO], 2017-2019.
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.

Column k=0 of A102892 and column k=0 of A102593.

Cf. A001764, A006013.

a:=proc(n) if n=0 then 1 else 5*binomial(3*n-1,n-2)/(3*n-1) fi end:
seq(a(n), n=0..25);
# Recurrence:
a := proc(n) option remember; if n < 3 then return [1,0,1][n+1] fi;
(27*n^3 - 81*n^2 + 78*n - 24)*a(n - 1)/(4*n^3 - 6*n^2 - 4*n) end:
seq(a(n), n=0..23); # Peter Luschny, Aug 08 2020
alias(PS=ListTools:-PartialSums): A102893List := proc(m) local A, P, n;
A := [1,0]; P := [1]; for n from 1 to m - 2 do P := PS(PS([op(P), P[-1]]));
A := [op(A), P[-2]] od; A end: A102893List(23); # Peter Luschny, Mar 26 2022

a[0] = 1; a[n_] := 5*Binomial[3n-1, n-2]/(3n-1); Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Mar 01 2018 *)

a(n) = if(n<=1, n==0, 5*binomial(3*n-1, n-2)/(3*n-1)); \\ Andrew Howroyd, Nov 17 2017

a(0)=1; a(n) = 5*binomial(3n-1, n-2)/(3n-1) if n > 0.
G.f.: g - z*g^2, where g = 1 + z*g^3 is the g.f. of the ternary numbers (A001764).
a(n) = A001764(n) - A006013(n-1).
D-finite with recurrence 2*n*(2*n+1)*(n-2)*a(n) -3*(n-1)*(3*n-4)*(3*n-2)*a(n-1)=0. - R. J. Mathar, Feb 16 2018
a(n) ~ (5*3^(3*n + 1/2))/(36*4^n*n^(3/2)*sqrt(Pi)). - Peter Luschny, Aug 08 2020

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.

Original entry on oeis.org

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

Emeric Deutsch

nonn

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)

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

Column k=1 of A102892.

Cf. A006013.

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

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

a(n)=(19*n-31)*binomial(3*n-8, n-4)/(n-1)/(2*n-3); /* Joerg Arndt, Mar 07 2013 */

concat(0, Vec((g->g^3*(3-2*g))(serreverse(x-2*x^2+x^3 + O(x^25))))) \\ Andrew Howroyd, Nov 12 2017

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

cp's OEIS Frontend

A102893 Number of noncrossing trees with n edges and having degree of the root at least 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula