A102593 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges in which the maximum number of contiguous border edges starting from the root in counterclockwise direction is equal to k.

1, 0, 1, 1, 1, 1, 5, 4, 2, 1, 25, 18, 8, 3, 1, 130, 88, 37, 13, 4, 1, 700, 455, 185, 63, 19, 5, 1, 3876, 2448, 973, 325, 97, 26, 6, 1, 21945, 13566, 5304, 1748, 518, 140, 34, 7, 1, 126500, 76912, 29697, 9690, 2856, 775, 193, 43, 8, 1, 740025, 444015, 169763, 54967

Offset

0,7

Comments

Row n has n+1 terms. Row sums yield the ternary numbers (A001764). T(n,0)=A102893(n).

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1274

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

Formula

T(n, k) = (k+1)binomial(3n-2k, n-k)/(2n-k+1) - (k+2)binomial(3n-2k-2, n-k-1)/(2n-k) if n > 1, 0 <= k <= n; T(1, 1)=1; T(0, 0)=1; T(n, k)=0 if k > n.

G.f.: G(t, z) = g(1-zg)/(1-tzg), where g = 1+zg^3 is the g.f. for the ternary numbers (A001764).

Example

T(2,0) = T(2,1) = T(2,2) = 1 because in _\, /\ and /_ the maximum number of contiguous border edges starting from the root in counterclockwise direction is 0,1 and 2, respectively.
Triangle starts:
    1;
    0,   1;
    1,   1,   1;
    5,   4,   2,  1;
   25,  18,   8,  3,  1;
  130,  88,  37, 13,  4, 1;
  700, 455, 185, 63, 19, 5, 1;
  ...

Maple

T:=proc(n, k) if n=0 and k=0 then 1 elif n=1 and k=1 then 1 elif k<=n then (k+1)*binomial(3*n-2*k, n-k)/(2*n-k+1)-(k+2)*binomial(3*n-2*k-2, n-k-1)/(2*n-k) else 0 fi end: for n from 0 to 10 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Mathematica

T[n_ /; n>1, k_] /; 0 <= k <= n := (k + 1) Binomial[3n - 2k, n - k]/(2n - k + 1) - (k + 2) Binomial[3n - 2k - 2, n - k - 1]/(2n - k); T[1, 1] = T[0, 0] = 1; T[_, _] = 0;
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 06 2018 *)

Prog

(PARI) T(n, k) = {if(n==0, k==0, if(k<=n, (k+1)*binomial(3*n-2*k, n-k)/(2*n-k+1)-(k+2)*binomial(3*n-2*k-2, n-k-1)/(2*n-k)))} \\ Andrew Howroyd, Nov 06 2017

Crossrefs

Cf. A001764, A102893, A006629.

Sequence in context: A085917 A180130 A242600 * A090462 A246966 A081749

Adjacent sequences: A102590 A102591 A102592 * A102594 A102595 A102596

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 22 2005

Status

approved