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!)
A045741 Number of edges in all noncrossing connected graphs on n nodes on a circle. 4
1, 9, 82, 765, 7266, 69930, 679764, 6659037, 65635570, 650194974, 6467730204, 64562259762, 646399361076, 6488447895540, 65276186864232, 657998685456093, 6644370824416530, 67198463606576790, 680568874690989900 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,2

LINKS

G. C. Greubel, Table of n, a(n) for n = 2..980

Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. vol. 116 (2006) pp. 135-144

I. M. Gessel, A short proof of the Deutsch-Sagan congruence for connected non crossing graphs, arXiv preprint arXiv:1403.7656, 2014

FORMULA

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

a(n) = 1 mod 3 if n in A103457; a(n) = 0 mod 3 otherwise [Eu et al.]. - R. J. Mathar, Feb 27 2008

Recurrence: (n-2)*(n-1)*(6*n-17)*a(n) = 18*(n-2)*a(n-1) + 12*(3*n-8)*(3*n-7)*(6*n-11)*a(n-2). - Vaclav Kotesovec, Dec 29 2012

a(n) ~ (sqrt(3)-1)/sqrt(Pi) * (2^(n-5/2)*3^(3*n/2-3/2))/sqrt(n). - Vaclav Kotesovec, Dec 29 2012

A244038(n) = a(n) + A244039(n) [Gessel]. - N. J. A. Sloane, Jun 28 2014

EXAMPLE

a(3)=9; indeed, with vertices u, v, w, the noncrossing connected graphs are {uv,uw}, {vu, vw}, {wu, wv}, and {uv, vw, wu} with a total of 9 edges.

MAPLE

A045741 := proc(n) local k ; add(binomial(3*n-3, n+k)*binomial(k, n-1), k=0..2*n-3) ; end: seq(A045741(n), n=2..20) ; # R. J. Mathar, Feb 27 2008

MATHEMATICA

Table[Sum[k*Binomial[3*n - 3, n + k]*Binomial[k - 1, k - n + 1], {k, n - 1, 2*n}]/(n - 1), {n, 2, 50}] (* G. C. Greubel, Jan 30 2017 *)

PROG

(PARI) for(n=2, 50, print1(sum(k=n-1, 2*n, k*binomial(3*n-3, n+k)* binomial(k-1, k-n+1))/(n-1), ", ")) \\ G. C. Greubel, Jan 30 2017

CROSSREFS

Cf. A007297, A244038, A244039.

Sequence in context: A081191 A060531 A248848 * A283498 A294956 A294645

Adjacent sequences:  A045738 A045739 A045740 * A045742 A045743 A045744

KEYWORD

nonn

AUTHOR

Emeric Deutsch

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 August 4 20:28 EDT 2021. Contains 346455 sequences. (Running on oeis4.)