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

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.

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.

Example

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

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

Prog

(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

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.

Sequence in context: A341725 A258239 A133176 * A152474 A088814 A088729

Adjacent sequences: A089432 A089433 A089434 * A089436 A089437 A089438

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 28 2003

Extensions

Keyword tabl added by Michel Marcus, Apr 09 2013

Status

approved