2,2

The number of non-crossing connected graphs on n nodes on a circle is given in A007297.

Andrew Howroyd, Table of n, a(n) for n = 2..200

P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.

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

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.

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

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 *)

(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

Cf. A143022, A007297.

Sequence in context: A186654 A390714 A152107 * A078009 A127848 A113573

Adjacent sequences: A143020 A143021 A143022 * A143024 A143025 A143026

Emeric Deutsch, Jul 30 2008

approved