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!)
A065065 Number of noncrossing connected graphs with nodes on a circle having n edges. 2
1, 3, 13, 64, 341, 1913, 11132, 66573, 406653, 2526351, 15913347, 101396034, 652378120, 4232439734, 27657380019, 181872596607, 1202641671293, 7991878198287, 53343146808137, 357464739709920, 2404073823950915 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

FORMULA

a(n) = Sum_{k=ceiling((n+3)/2)..n+1} binomial(3*k-3,n+k)*binomial(n-1,n-k+1)/(k-1).

G.f. satisfies: A(x) = x*(1+3*A(x)+4*A(x)^2+A(x)^3). - Vladimir Kruchinin, Nov 12 2014

a(n) = Sum_{m=n..2*n-2} A127537(m,n). - Andrew Howroyd, Nov 12 2017

EXAMPLE

a(3)=13 because we have 1 triangle on 3 nodes and 12 non-crossing trees on 4 nodes.

MAPLE

A065065 := n-> sum(binomial(3*k-3, n+k)*binomial(n-1, n-k+1)/(k-1), k=ceil((n+3)/2)..n+1);

MATHEMATICA

terms = 21;

A[_] = 0;

Do[A[x_] = x (1 + 3 A[x] + 4 A[x]^2 + A[x]^3) + O[x]^(terms+1), {terms+1}];

CoefficientList[A[x]/x, x] (* Jean-Fran├žois Alcover, Jul 29 2018, after Vladimir Kruchinin *)

PROG

(PARI) a(n)=sum(k=ceil((n+3)/2), n+1, binomial(3*k-3, n+k)*binomial(n-1, n-k+1)/(k-1)); \\ Andrew Howroyd, Nov 12 2017

(PARI) Vec(serreverse(x/(1+3*x+4*x^2+x^3) + O(x^20))) \\ Andrew Howroyd, Nov 12 2017

CROSSREFS

Cf. A007297, A127537.

Sequence in context: A283667 A011272 A200719 * A020086 A151987 A126149

Adjacent sequences:  A065062 A065063 A065064 * A065066 A065067 A065068

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Nov 06 2001

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 May 28 21:37 EDT 2020. Contains 334690 sequences. (Running on oeis4.)