A089434 Triangle read by rows: T(n,k) (n >= 2, k >= 0) is the number of non-crossing connected graphs on n nodes on a circle, having k interior faces. Rows are indexed 2,3,4,...; columns are indexed 0,1,2,....

1, 3, 1, 12, 9, 2, 55, 66, 30, 5, 273, 455, 315, 105, 14, 1428, 3060, 2856, 1428, 378, 42, 7752, 20349, 23940, 15960, 6300, 1386, 132, 43263, 134596, 191268, 159390, 83490, 27324, 5148, 429, 246675, 888030, 1480050, 1480050, 965250, 418275, 117117

Offset: 2

Author

Emeric Deutsch, Dec 28 2003

Keywords

• nonn
• tabl

Examples

			T(4,1)=9 because, considering the complete graph K_4 on the nodes A,B,C and D, we obtain a non-crossing connected graph on A,B,C,D, with exactly one interior face, by deleting either both diagonals AC and BD (1 case) or deleting one of the two diagonals and one of the four sides (8 cases).
Triangle starts:
   1;
   3,  1;
  12,  9,  2;
  55, 66, 30, 5;
  ... - _Michel Marcus_, Apr 09 2013
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 2..1276
• P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
• V. Pilaud, J. Rue, Analytic combinatorics of chord and hyperchord diagrams with k crossings, Adv. Appl. Math. 57 (2014) 60-100, equation (3).

Crossrefs

T(n, n-2) yields the Catalan numbers (A000108) corresponding to triangulations, T(n, 0) yields the ternary numbers (A001764) corresponding to noncrossing trees, T(n, 1) yields A003408, row sums yield A007297. Sum(kT(n, k), k=0..n-2) yields A045742.

Columns k=0..2 are A001764, A003408, A089433.

Cf. A007297, A000108, A108410.

Programs

Mathematica

t[n_, k_] = Binomial[n + k - 2, k] Binomial[3 n - 3, n - 2 - k]/(n - 1) ; Flatten[Table[t[n, k], {n, 2, 10}, {k, 0, n - 2}]][[;; 43]]
(* Jean-François Alcover, Jun 30 2011 *)

PARI

T(n, k)={binomial(n+k-2, k)*binomial(3*n-3, n-2-k)/(n-1)}
for(n=2, 10, for(k=0, n-2, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017

Formula

T(n, k) = binomial(n+k-2, k)*binomial(3*n-3, n-2-k)/(n-1), 0 <= k <= n-2.

G.f.: G(t, z) satisfies G^3 + t*G^2 - (1+2*t)*z*G+(1+t)*z^2 = 0.

O.g.f. equals the series reversion w.r.t. x of x*(1-x*t)/(1+x)^3. If R(n,t) is the n-th row polynomial of this triangle then R(n,t-1) is the n-th row polynomial of A108410. - Peter Bala, Jul 15 2012

Extensions

Keyword tabl added by Michel Marcus, Apr 09 2013

Offset corrected by Andrew Howroyd, Nov 17 2017