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
Keywords
Examples
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.
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
Programs
-
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 *) -
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
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