A045741 Number of edges in all noncrossing connected graphs on n nodes on a circle.

1, 9, 82, 765, 7266, 69930, 679764, 6659037, 65635570, 650194974, 6467730204, 64562259762, 646399361076, 6488447895540, 65276186864232, 657998685456093, 6644370824416530, 67198463606576790, 680568874690989900

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