login
The OEIS is supported by the many generous donors to the OEIS 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. 4

%I #26 Jul 26 2022 12:52:58

%S 1,3,13,64,341,1913,11132,66573,406653,2526351,15913347,101396034,

%T 652378120,4232439734,27657380019,181872596607,1202641671293,

%U 7991878198287,53343146808137,357464739709920,2404073823950915

%N Number of noncrossing connected graphs with nodes on a circle having n edges.

%H Andrew Howroyd, <a href="/A065065/b065065.txt">Table of n, a(n) for n = 1..200</a>

%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of non-crossing configurations</a>, Discrete Math., 204, 203-229, 1999.

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

%F G.f. satisfies: A(x) = x*(1+3*A(x)+4*A(x)^2+A(x)^3). - _Vladimir Kruchinin_, Nov 12 2014

%F a(n) = Sum_{m=n..2*n-2} A127537(m,n). - _Andrew Howroyd_, Nov 12 2017

%F D-finite with recurrence 8*n*(2*n+1)*a(n) +2*(-46*n^2+55*n-18)*a(n-1) +6*(-30*n^2+60*n-7)*a(n-2) +2*(n-3)*(28*n-163)*a(n-3) +93*(n-3)*(n-4)*a(n-4)=0. - _R. J. Mathar_, Jul 26 2022

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

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

%t terms = 21;

%t A[_] = 0;

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

%t CoefficientList[A[x]/x, x] (* _Jean-François Alcover_, Jul 29 2018, after _Vladimir Kruchinin_ *)

%o (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

%o (PARI) Vec(serreverse(x/(1+3*x+4*x^2+x^3) + O(x^20))) \\ _Andrew Howroyd_, Nov 12 2017

%Y Cf. A007297, A127537.

%K nonn

%O 1,2

%A _Emeric Deutsch_, Nov 06 2001

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:59 EDT 2024. Contains 371268 sequences. (Running on oeis4.)