login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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
Cf. A001764.
Sequence in context: A316655 A318848 A193798 * A271862 A309373 A131401
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jan 15 2005 and Jan 17 2005
EXTENSIONS
Edited by N. J. A. Sloane, Jan 25 2009 at the suggestion of R. J. Mathar and Max Alekseyev
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)