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