cp's OEIS Frontend

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

%I A045741 #32 Jan 30 2017 21:42:59
%S A045741 1,9,82,765,7266,69930,679764,6659037,65635570,650194974,6467730204,
%T A045741 64562259762,646399361076,6488447895540,65276186864232,
%U A045741 657998685456093,6644370824416530,67198463606576790,680568874690989900
%N A045741 Number of edges in all noncrossing connected graphs on n nodes on a circle.
%H A045741 G. C. Greubel, <a href="/A045741/b045741.txt">Table of n, a(n) for n = 2..980</a>
%H A045741 Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, <a href="http://dx.doi.org/10.1111/j.1467-9590.2006.00337.x">On the congruences of some combinatorial numbers</a>, Stud. Appl. Math. vol. 116 (2006) pp. 135-144
%H A045741 I. M. Gessel, <a href="http://arxiv.org/abs/1403.7656">A short proof of the Deutsch-Sagan congruence for connected non crossing graphs</a>, arXiv preprint arXiv:1403.7656, 2014
%F A045741 a(n) = Sum_{k = n-1 .. 2*n} (k*binomial(3*n-3, n+k)*binomial(k-1, k-n+1))/(n-1).
%F A045741 a(n) = 1 mod 3 if n in A103457; a(n) = 0 mod 3 otherwise [Eu et al.]. - _R. J. Mathar_, Feb 27 2008
%F A045741 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
%F A045741 a(n) ~ (sqrt(3)-1)/sqrt(Pi) * (2^(n-5/2)*3^(3*n/2-3/2))/sqrt(n). - _Vaclav Kotesovec_, Dec 29 2012
%F A045741 A244038(n) = a(n) + A244039(n) [Gessel]. - _N. J. A. Sloane_, Jun 28 2014
%e A045741 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.
%p A045741 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
%t A045741 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 *)
%o A045741 (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
%Y A045741 Cf. A007297, A244038, A244039.
%K A045741 nonn
%O A045741 2,2
%A A045741 _Emeric Deutsch_