|
| |
|
|
A143023
|
|
Sum of the root degrees over all non-crossing connected graphs on n nodes on a circle (by root we mean a distinguished node).
|
|
2
|
|
|
|
1, 6, 41, 306, 2422, 19980, 169941, 1479786, 13127114, 118217268, 1077955034, 9932655348, 92342765868, 865126386072, 8159523358029, 77411610053658, 738263424935170, 7073522484902820, 68056887469098990, 657269559836605980
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,2
|
|
|
COMMENTS
|
The number of non-crossing connected graphs on n nodes on a circle is given in A007297.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = (L(n-2, 3n-2, n+1) + L(n-3, 3n-3, n))/(n-1) where L(p,q,r)=[u^p](1+u)^q/(1-u)^r = Sum_{i=0..min(p,q)} binomial(q,i) * binomial(r+p-1-i, r-1).
G.f.: zG(1+G)/(1-G) where G=G(z) satisfies G(1-G)=z(1+G)^3.
a(n) = Sum_{k=1..n-1} k*A143022(n,k).
D-finite with recurrence 5*n*(n-1)*a(n) -18*(n-1)*(n-3)*a(n-1) +12*(-45*n^2+180*n-178)*a(n-2) +216*(3*n-10)*(3*n-11)*a(n-3)=0. - R. J. Mathar, Jul 26 2022
|
|
|
EXAMPLE
|
a(3)=6 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the root, say A, has degrees 2, 2, 1 and 1, respectively.
|
|
|
MAPLE
|
eq:=G*(1-G)-z*(1+G)^3: G:=RootOf(eq, G): Gser:=series(z*G*(1+G)/(1-G), z=0, 25): seq(coeff(Gser, z, n), n=2..21); # end
L:=proc(p, q, r) options operator, arrow: sum(binomial(q, i)*binomial(r+p-1-i, r-1), i=0..min(p, q)) end proc: a:=proc(n) options operator, arrow: (L(n-2, 3*n-2, n+1)+L(n-3, 3*n-3, n))/(n-1) end proc: seq(a(n), n=2..21);
|
|
|
MATHEMATICA
|
L[p_, q_, r_] := Sum[ Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; t[n_, k_] := 2^(k-1)*(k*L[n - k - 1, 3*n - k - 4, n - 2] - L[n - k - 2, 3*n - k - 3, n-1])/(n-1); t[2, 1] = 1; a[n_] := Sum[ k*t[n, k], {k, 1, n-1}]; Table[a[n], {n, 2, 21}] (* Jean-François Alcover, Oct 05 2011, after Maple *)
|
|
|
PROG
|
(PARI) {my(n=25); my(g=serreverse(x*(1-x)/(1+x)^3 + O(x*x^n))); Vec(g*(1+g)/(1-g))} \\ Andrew Howroyd, Dec 22 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
