|
| |
|
|
A045741
|
|
Number of edges in all noncrossing connected graphs on n nodes on a circle.
|
|
5
|
|
|
|
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
|
|
|
|
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
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
