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

Author

Emeric Deutsch, Jan 16 2005

Keywords

• nonn
• tabl

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.

Examples

			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;
  ...
		

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.

Crossrefs

Cf. A001764, A102893, A030983.

Programs

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
				

Mathematica

T[n_, k_] := Which[n == 0 && k == 0, 1, k == 0, 5*Binomial[3n - 1, n - 2]/(3n - 1), kJean-François Alcover, Jul 06 2018, from Maple *)

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

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