A143021 - OEIS

%I #17 Jul 22 2022 13:01:54

%S 2,6,36,270,2244,19740,179880,1678446,15927780,153055188,1485010488,

%T 14518525164,142821228648,1412109087480,14021321053392,

%U 139725123309486,1396698760714788,13998927825197220,140638610864578200

%N Number of vertices of degree 1 in all non-crossing connected graphs on n points on a circle.

%H Andrew Howroyd, <a href="/A143021/b143021.txt">Table of n, a(n) for n = 2..200</a>

%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of noncrossing configurations</a>, Discrete Math. 204 (1999), 203-229.

%F a(n) = n*A089436(n).

%F 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).

%F 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

%e 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}.

%p 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);

%t terms = 19;

%t g[x_] = 0; Do[g[x_] = g[x]^2 + x (1+g[x])^3 + O[x]^(terms+2), {terms+2}];

%t Drop[CoefficientList[(x+x g[x])^2+O[x]^(terms+2), x], 2] Range[2, terms+1] (* _Jean-François Alcover_, Jul 29 2018, after A089436 and _Andrew Howroyd_ *)

%o (PARI) { my(n=30); Vec(deriv((x+x*serreverse((x-x^2)/(1+x)^3 + O(x^n)))^2)) } \\ _Andrew Howroyd_, Dec 22 2017

%Y Cf. A007297, A089436.

%K nonn

%O 2,1

%A _Emeric Deutsch_, Jul 30 2008