

A101409


Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges in which the leftmost leaf is at level k.


1



1, 1, 2, 3, 5, 4, 12, 19, 16, 8, 55, 85, 73, 44, 16, 273, 416, 361, 234, 112, 32, 1428, 2156, 1883, 1269, 680, 272, 64, 7752, 11628, 10200, 7043, 4016, 1856, 640, 128, 43263, 64581, 56829, 39897, 23665, 11864, 4848, 1472, 256, 246675, 366850, 323587, 229936, 140161, 74050, 33360, 12256, 3328, 512
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



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



FORMULA

T(n,k) = Sum_{i=0..k1}((k+i)/(2*nk+i)) binomial(k1, i) binomial(3n2k+i1, nk).
G.f. = (1tzg^2)/(1tzgtzg^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/(1t*z*gt*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*n3, n1)/(2*n1) elif k<=n then sum(((k+i)/(2*nk+i))*binomial(k1, i)*binomial(3*n2*k+i1, nk), i=0..k1) 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)/(2nk+i) Binomial[k1, i] Binomial[3n2k+i1, nk], {i, 0, k1}]; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* JeanFrançois Alcover, Mar 18 2017 *)


PROG

(PARI) T(n, k)={sum(i=0, k1, ((k+i)/(2*nk+i))*binomial(k1, i)*binomial(3*n2*k+i1, nk))} \\ Andrew Howroyd, Nov 17 2017


CROSSREFS



KEYWORD



AUTHOR



EXTENSIONS



STATUS

approved



