A102892 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges in which the number of edges from the root to the first branch point is k.

1, 0, 1, 1, 0, 2, 5, 3, 0, 4, 25, 16, 6, 0, 8, 130, 83, 32, 12, 0, 16, 700, 442, 166, 64, 24, 0, 32, 3876, 2420, 884, 332, 128, 48, 0, 64, 21945, 13566, 4840, 1768, 664, 256, 96, 0, 128, 126500, 77539, 27132, 9680, 3536, 1328, 512, 192, 0, 256

Offset

0,6

Comments

The statistic "number of edges from the root to the first branchpoint" is equal to 0 if root is a branchpoint and it is equal to the total number of edges if there is no branchpoint.

Row n contains n+1 terms.

Row sums yield the ternary numbers (A001764).

Column 0 yields A102893.

Column 1 yields A030983.

Links

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

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

Formula

T(n, 0) = 5*binomial(3n-1, n-2)/(3n-1) for n > 0.

T(n, k) = [2^(k-1)/(n-k+1)]binomial(3n-3k+1, n-k)-[2^k/(n-k)]binomial(3n-3k-2, n-k-1) for 0 < k < n.

T(n, n) = 2^(n-1) (n > 0).

G.f.: (1/2)*g(2-g) + g^2*(1-2*z)/(2*(1-2*t*z)), where g = 1 + z*g^3 is the g.f. of the ternary numbers (A001764).

Example

T(2,0)=1 because we have /\ and T(2,2)=2 because we have /_ and _\.
Triangle starts:
    1;
    0,  1;
    1,  0,  2;
    5,  3,  0,  4;
   25, 16,  6,  0, 8;
  130, 83, 32, 12, 0, 16;
  ...

Maple

T:=proc(n, k) if n=0 and k=0 then 1 elif k=0 then 5*binomial(3*n-1, n-2)/(3*n-1) elif k<n then (2^(k-1)/(n-k+1))*binomial(3*n-3*k+1, n-k)-(2^k/(n-k))*binomial(3*n-3*k-2, n-k-1) elif k=n then 2^(n-1) 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_, k_] := Which[n == 0 && k == 0, 1, k == 0, 5*Binomial[3n - 1, n - 2]/(3n - 1), k<n, (2^(k-1)/(n - k + 1))*Binomial[3n - 3k + 1, n - k] - (2^k/(n-k))*Binomial[3n - 3k - 2, n - k - 1], k == n, 2^(n-1), True, 0];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 06 2018, from Maple *)

Prog

(PARI)
T(n, k) = {if(k==0, if(n==0, 1, 5*binomial(3*n-1, n-2)/(3*n-1)), if(n<=k, if(n==k, 2^(n-1), 0), 2^(k-1)*binomial(3*n-3*k+1, n-k)/(n-k+1) - 2^k*binomial(3*n-3*k-2, n-k-1)/(n-k)))}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 06 2017

Crossrefs

Cf. A001764, A102893, A030983.

Sequence in context: A160127 A361226 A011035 * A132898 A365728 A265318

Adjacent sequences: A102889 A102890 A102891 * A102893 A102894 A102895

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 16 2005

Status

approved