A089433 Number of noncrossing connected graphs on n nodes having exactly two interior faces.

2, 30, 315, 2856, 23940, 191268, 1480050, 11196900, 83304936, 611931320, 4450217772, 32104210320, 230080173960, 1639890119016, 11634355574100, 82216112723640, 579022013389050, 4065827626164150, 28475852003986695

Offset

4,1

Links

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

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

Formula

a(n) = n*binomial(3n-3, n-4)/2.

D-finite with recurrence -2*(2*n+1)*(n-4)*a(n) +3*(3*n-4)*(3*n-5)*a(n-1)=0. - R. J. Mathar, Jul 26 2022

Example

a(4)=2 because the only connected graphs on the nodes A,B,C,D having exactly two interior faces are {AB,BC,CD,DA,AC} and {AB,BC,CD,DA,BD}.

Prog

(PARI) a(n) = n*binomial(3*n-3, n-4)/2; \\ Michel Marcus, Oct 26 2015

Crossrefs

Column k=2 of A089434.

Cf. A007297.

Sequence in context: A189770 A245020 A277660 * A152277 A230610 A231597

Adjacent sequences: A089430 A089431 A089432 * A089434 A089435 A089436

Keyword

nonn

Author

Emeric Deutsch, Dec 28 2003

Status

approved