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, 198980197653837600, 1387582317108496080, 9658661226931688400

Offset

4,1

Links

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

Philippe Flajolet and Marc Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., Vol. 204, No. 1-3 (1999), 203-229.

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

a(n) ~ 3^(3*n-5/2) * sqrt(n/Pi) / 2^(2*n+3). - Amiram Eldar, Nov 01 2025

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

Mathematica

a[n_] := n * Binomial[3*n-3, n-4]/2; Array[a, 22, 4] (* Amiram Eldar, Nov 01 2025 *)

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,easy

Author

Emeric Deutsch, Dec 28 2003

Status

approved