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, Discr. Math. 204 (1999), 203-229.
FORMULA
T(n,k) = 2^(k-1)*(k*L(n-k-1, 3n-k-4, n-2) - L(n-k-2, 3n-k-3, 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) = g*(z - t*(g-z))/(g - 2*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 - 3*z*g + 2*z^2 = 0 (A007297).
EXAMPLE
T(3,1)=2, T(3,2)=2 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the node A has degrees 2, 2, 1 and 1, respectively.
Triangle starts:
1;
2, 2;
9, 10, 4;
54, 62, 32, 8;
374, 436, 248, 88, 16;
2820, 3316, 1984, 816, 224, 32;
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: 2^(k-1)*(k*L(n-k-1, 3*n-k-4, n-2)-L(n-k-2, 3*n-k-3, 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
L[p_, q_, r_] := Sum[Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; t[n_, k_] := 2^(k-1)*(k*L[n - k - 1, 3*n - k - 4, n - 2] - L[n - k - 2, 3*n - k - 3, n-1])/(n-1); t[2, 1] = 1; Flatten[ Table[t[n, k], {n, 2, 10}, {k, 1, n-1}]] (* Jean-François Alcover, Oct 05 2011, after Maple *)
PROG
(PARI)
L(p, q, r)={sum(i=0, min(p, q), binomial(q, i)*binomial(r+p-1-i, r-1))}
T(n, k)={if(n<3, n==2&&k==1, 2^(k-1)*(k*L(n-k-1, 3*n-k-4, n-2) - L(n-k-2, 3*n-k-3, n-1))/(n-1))}
for(n=2, 10, for(k=1, n-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017
(PARI)
S(n)={my(g=x+x*serreverse((x-x^2)/(1+x)^3 + O(x^n))); Vec(g*(x - y*(g-x))/(g - 2*y*(g - x)))}
my(v=S(10)); for(n=2, #v, my(p=v[n]); for(k=1, n-1, print1(polcoeff(p, k), ", ")); print) \\ Andrew Howroyd, Nov 17 2017
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jul 30 2008
STATUS
approved