OFFSET
1,3
COMMENTS
T(n,k) is also the number of diagonally convex directed polyominoes with n diagonals and having k diagonals of length 1. Proof: the two triangles have the same g.f.
Row n has n terms. Column 1 and row sums yield the ternary numbers (A001764).
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1275
M. Bousquet-Mélou, Percolation models and animals, Europ. J. Combinatorics, 17, 1996, 343-369 (Prop. 2.4).
E. Deutsch, S. Feretic and M. Noy, Diagonally convex directed polyominoes and even trees: a bijection and related issues, Discrete Math., 256 (2002), 645-654.
FORMULA
T(n,k) = Sum_{i=0..k-1}((k+i)/(2*n-k+i)) binomial(k-1, i) binomial(3n-2k+i-1, n-k).
G.f. = (1-tzg^2)/(1-tzg-tzg^2), where g=1+zg^3 is the g.f. of the ternary numbers (A001764). (An explicit expression for g is given in the Maple program.)
EXAMPLE
T(2,1)=1 and T(2,2)=2 because the noncrossing trees with 2 edges are /\, /_ and _\.
Or, T(2,2)=2 because the horizontal domino and the vertical domino have 2 diagonals of length 1 each.
Triangle begins:
1;
1, 2;
3, 5, 4;
12, 19, 16, 8;
55, 85, 73, 44, 16;
MAPLE
G:=t*z*g/(1-t*z*g-t*z*g^2): g:=2*sin(arcsin(3*sqrt(3*z)/2)/3)/sqrt(3*z): Gser:=simplify(series(G, z=0, 12)): Gser:=simplify(series(G, z=0, 14)): for n from 1 to 10 do P[n]:=sort(coeff(Gser, z^n)) od: for n from 1 to 10 do seq(coeff(P[n], t^k), k=1..n) od;
T:=proc(n, k) if k=1 then binomial(3*n-3, n-1)/(2*n-1) elif k<=n then sum(((k+i)/(2*n-k+i))*binomial(k-1, i)*binomial(3*n-2*k+i-1, n-k), i=0..k-1) else 0 fi end: for n from 1 to 10 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
MATHEMATICA
T[n_, k_] := Sum[(k+i)/(2n-k+i) Binomial[k-1, i] Binomial[3n-2k+i-1, n-k], {i, 0, k-1}]; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 18 2017 *)
PROG
(PARI) T(n, k)={sum(i=0, k-1, ((k+i)/(2*n-k+i))*binomial(k-1, i)*binomial(3*n-2*k+i-1, n-k))} \\ Andrew Howroyd, Nov 17 2017
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jan 15 2005 and Jan 17 2005
EXTENSIONS
STATUS
approved