A101409 - OEIS

%I #17 Nov 18 2017 00:22:46

%S 1,1,2,3,5,4,12,19,16,8,55,85,73,44,16,273,416,361,234,112,32,1428,

%T 2156,1883,1269,680,272,64,7752,11628,10200,7043,4016,1856,640,128,

%U 43263,64581,56829,39897,23665,11864,4848,1472,256,246675,366850,323587,229936,140161,74050,33360,12256,3328,512

%N 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.

%C 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.

%C Row n has n terms. Column 1 and row sums yield the ternary numbers (A001764).

%H Andrew Howroyd, <a href="/A101409/b101409.txt">Table of n, a(n) for n = 1..1275</a>

%H M. Bousquet-Mélou, <a href="http://dx.doi.org/10.1006/eujc.1996.0029">Percolation models and animals</a>, Europ. J. Combinatorics, 17, 1996, 343-369 (Prop. 2.4).

%H E. Deutsch, S. Feretic and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00340-0">Diagonally convex directed polyominoes and even trees: a bijection and related issues</a>, Discrete Math., 256 (2002), 645-654.

%F 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).

%F 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.)

%e T(2,1)=1 and T(2,2)=2 because the noncrossing trees with 2 edges are /\, /_ and _\.

%e Or, T(2,2)=2 because the horizontal domino and the vertical domino have 2 diagonals of length 1 each.

%e Triangle begins:

%e    1;

%e    1,  2;

%e    3,  5,  4;

%e   12, 19, 16,  8;

%e   55, 85, 73, 44, 16;

%p 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;

%p 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

%t 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 *)

%o (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

%Y Cf. A001764.

%K nonn,tabl

%O 1,3

%A _Emeric Deutsch_, Jan 15 2005 and Jan 17 2005

%E Edited by _N. J. A. Sloane_, Jan 25 2009 at the suggestion of _R. J. Mathar_ and _Max Alekseyev_