OFFSET
2,2
LINKS
Andrew Howroyd, Table of n, a(n) for n = 2..1276
P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.
FORMULA
T(n,k) = k*L(n-k-1, 3n-k-4, n-1)/(n-1) (n >= 2, 1 <= k <= n-1), where L(p,q,r) = [u^p](1+u)^q/(1-u)^r = Sum_{i=0..min(p,q)} binomial(q,i)*binomial(r+p-1-i, r-1).
G.f.: G(t,z) = zg/[g - t*(g - z)], where g=g(z), the g.f. for the number of non-crossing connected graphs on n nodes on a circle, satisfies g^3 + g^2 - 3z*g + 2*z^2 = 0 (A007297).
T(n,k) = k*Sum_{i=0..min(n-k-1, 3*n-k-4)} binomial(3*n-k-4, i)*binomial(2*n-k-i-3, n-2)/(n-1). - Andrew Howroyd, Nov 17 2017
EXAMPLE
T(3,1)=3 and T(3,2)=1 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the distances from A to B are 1, 1, 1 and 2, respectively.
Triangle starts:
1;
3, 1;
16, 6, 1;
105, 41, 9, 1;
768, 306, 75, 12, 1;
...
MAPLE
L:=proc(p, q, r) options operator, arrow: sum(binomial(q, i)*binomial(r+p-1-i, r-1), i=0..min(p, q)) end proc: T:=proc(n, k) options operator, arrow: k*L(n-k-1, 3*n-k-4, n-1)/(n-1) end proc: for n from 2 to 10 do seq(T(n, k), k=1..n-1) end do; # yields sequence in triangular form
MATHEMATICA
t[n_, k_] := k*L[n - k - 1, 3*n - k - 4, n-1]/(n-1); L[p_, q_, r_] := Sum[ Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; Flatten[ Table[ t[n, k], {n, 2, 10}, {k, 1, n-1}]] (* Jean-François Alcover, Oct 05 2011, Oct 05 2011, after Maple *)
PROG
(PARI)
T(n, k)=k*sum(i=0, min(n-k-1, 3*n-k-4), binomial(3*n-k-4, i)*binomial(2*n-k-i-3, n-2))/(n-1);
for(n=2, 10, for(k=1, n-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jul 30 2008
STATUS
approved