cp's OEIS Frontend

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

%I A089435 #27 Nov 18 2017 01:40:45
%S A089435 1,3,1,13,8,2,66,60,25,5,367,442,255,84,14,2164,3248,2380,1064,294,42,
%T A089435 13293,23904,21192,11832,4410,1056,132,84157,176397,183303,122115,
%U A089435 56430,18216,3861,429,545270,1305480,1554850,1200320,657195,262262,75075
%N 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,....
%H A089435 Andrew Howroyd, <a href="/A089435/b089435.txt">Table of n, a(n) for n = 2..1276</a>
%H A089435 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 A089435 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 A089435 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 A089435 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 A089435 Triangle starts:
%e A089435     1;
%e A089435     3,   1;
%e A089435    13,   8,   2;
%e A089435    66,  60,  25,   5;
%e A089435   367, 442, 255,  84,  14;
%e A089435   ...
%t A089435 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 A089435 Flatten[Table[t[n, k], {n, 2, 10}, {k, 0, n-2}]][[1 ;; 43]] (* _Jean-François Alcover_, Jun 20 2011 *)
%o A089435 (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 A089435 T(n, n-2) yields the Catalan numbers (A000108) corresponding to triangulations, T(n, 0) yields A045743, row sums yield A007297.
%Y A089435 Cf. A007297, A000108, A045743.
%K A089435 nonn,tabl
%O A089435 2,2
%A A089435 _Emeric Deutsch_, Dec 28 2003
%E A089435 Keyword tabl added by _Michel Marcus_, Apr 09 2013