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

Author

Emeric Deutsch, Jan 16 2005

Keywords

• nonn
• easy

Comments

[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

Examples

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

Links

• 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.

Crossrefs

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

Cf. A001764, A006013.

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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