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,4

Comments

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

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.

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

Example

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

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

Prog

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

Crossrefs

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

Cf. A001764, A006013.

Sequence in context: A182626 A351050 A184139 * A094602 A207834 A351187

Adjacent sequences: A102890 A102891 A102892 * A102894 A102895 A102896

Keyword

nonn,easy

Author

Emeric Deutsch, Jan 16 2005

Status

approved