A102892 - OEIS

%I #20 Jul 06 2018 08:51:12

%S 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,

%T 0,32,3876,2420,884,332,128,48,0,64,21945,13566,4840,1768,664,256,96,

%U 0,128,126500,77539,27132,9680,3536,1328,512,192,0,256

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

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

%C Row n contains n+1 terms.

%C Row sums yield the ternary numbers (A001764).

%C Column 0 yields A102893.

%C Column 1 yields A030983.

%H Andrew Howroyd, <a href="/A102892/b102892.txt">Table of n, a(n) for n = 0..1274</a>

%H M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00121-0">Enumeration of noncrossing trees on a circle</a>, Discrete Math., 180, 301-313, 1998.

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

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

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

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

%e T(2,0)=1 because we have /\ and T(2,2)=2 because we have /_ and _\.

%e Triangle starts:

%e     1;

%e     0,  1;

%e     1,  0,  2;

%e     5,  3,  0,  4;

%e    25, 16,  6,  0, 8;

%e   130, 83, 32, 12, 0, 16;

%e   ...

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

%t 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];

%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jul 06 2018, from Maple *)

%o (PARI)

%o 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)))}

%o for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Nov 06 2017

%Y Cf. A001764, A102893, A030983.

%K nonn,tabl

%O 0,6

%A _Emeric Deutsch_, Jan 16 2005