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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Dec 28 2003
EXTENSIONS
Keyword tabl added by Michel Marcus, Apr 09 2013
STATUS
approved