|
|
A143021
|
|
Number of vertices of degree 1 in all non-crossing connected graphs on n points on a circle.
|
|
1
|
|
|
2, 6, 36, 270, 2244, 19740, 179880, 1678446, 15927780, 153055188, 1485010488, 14518525164, 142821228648, 1412109087480, 14021321053392, 139725123309486, 1396698760714788, 13998927825197220, 140638610864578200
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
LINKS
|
|
|
FORMULA
|
G.f.: z*(d/dz)g^2, where g=g(z), the g.f. for the number of non-crossing connected graphs on n nodes on a circle, satisfies g^3 + g^2 - 3zg + 2z^2 = 0 (A007297).
D-finite with recurrence (n-1)*(n-2)*a(n) -34*(n-2)*(n-4)*a(n-1) +4*(29*n^2-396*n+937)*a(n-2) +24*(153*n^2-1071*n+1810)*a(n-3) -2688*(3*n-14)*(3*n-16)*a(n-4)=0. - R. J. Mathar, Jul 22 2022
|
|
EXAMPLE
|
a(3)=6 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the vertices of degree 1 are (none), {B,C}, {A,C} and {A,B}.
|
|
MAPLE
|
g:=-1/3+(2/3)*sqrt(1+9*z)*sin((1/3)*arcsin(((2+27*z+54*z^2)*1/2)/(1+9*z)^(3/2))): ser:=series(z*(diff(g^2, z)), z=0, 25): seq(coeff(ser, z, n), n=2..21);
|
|
MATHEMATICA
|
terms = 19;
g[x_] = 0; Do[g[x_] = g[x]^2 + x (1+g[x])^3 + O[x]^(terms+2), {terms+2}];
|
|
PROG
|
(PARI) { my(n=30); Vec(deriv((x+x*serreverse((x-x^2)/(1+x)^3 + O(x^n)))^2)) } \\ Andrew Howroyd, Dec 22 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|