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

%I #27 Nov 18 2017 01:40:45

%S 1,3,1,13,8,2,66,60,25,5,367,442,255,84,14,2164,3248,2380,1064,294,42,

%T 13293,23904,21192,11832,4410,1056,132,84157,176397,183303,122115,

%U 56430,18216,3861,429,545270,1305480,1554850,1200320,657195,262262,75075

%N 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,....

%H Andrew Howroyd, <a href="/A089435/b089435.txt">Table of n, a(n) for n = 2..1276</a>

%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of non-crossing configurations</a>, Discrete Math., 204, 203-229, 1999.

%F 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.

%F 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.

%e 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).

%e Triangle starts:

%e 1;

%e 3, 1;

%e 13, 8, 2;

%e 66, 60, 25, 5;

%e 367, 442, 255, 84, 14;

%e ...

%t 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) ;

%t Flatten[Table[t[n, k], {n, 2, 10}, {k, 0, n-2}]][[1 ;; 43]] (* _Jean-François Alcover_, Jun 20 2011 *)

%o (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

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

%Y Cf. A007297, A000108, A045743.

%K nonn,tabl

%O 2,2

%A _Emeric Deutsch_, Dec 28 2003

%E Keyword tabl added by _Michel Marcus_, Apr 09 2013