A089435 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 triangles. Rows are indexed 2,3,4,...; columns are indexed 0,1,2,....

1, 3, 1, 13, 8, 2, 66, 60, 25, 5, 367, 442, 255, 84, 14, 2164, 3248, 2380, 1064, 294, 42, 13293, 23904, 21192, 11832, 4410, 1056, 132, 84157, 176397, 183303, 122115, 56430, 18216, 3861, 429, 545270, 1305480, 1554850, 1200320, 657195, 262262, 75075

Offset: 2

Author

Emeric Deutsch, Dec 28 2003

Keywords

• nonn
• tabl

Examples

			T(4,1)=8 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 triangle, by deleting one of the two diagonals and one of the four sides (8 possibilities).
Triangle starts:
    1;
    3,   1;
   13,   8,   2;
   66,  60,  25,   5;
  367, 442, 255,  84,  14;
  ...
		

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.

Crossrefs

T(n, n-2) yields the Catalan numbers (A000108) corresponding to triangulations, T(n, 0) yields A045743, row sums yield A007297.

Cf. A007297, A000108, A045743.

Programs

Mathematica

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

PARI

T(n, k) = binomial(n+k-2, k)*sum(i=0,floor((n-k-2)/2),binomial(n+k+i-2, i)*binomial(3*n-3-k-i, 2*n-1+i))/(n-1); \\ Michel Marcus, Oct 26 2015

Formula

T(n, k) = binomial(n+k-2, k)*sum(binomial(n+k+i-2, i)*binomial(3*n-3-k-i, 2*n-1+i), i=0..floor((n-k-2)/2))/(n-1), n>=2, k>=0.

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

Extensions

Keyword tabl added by Michel Marcus, Apr 09 2013