|
%I #20 Nov 18 2017 00:22:58
%S 1,3,9,3,27,28,81,174,18,243,900,285,729,4185,2703,135,2187,18144,
%T 19908,3024,6561,74844,125496,38640,1134,19683,297432,711018,369696,
%U 32886,59049,1148175,3725190,2943090,528930,10206,177147,4330260,18379548,20588040,6228585,363528
%N Triangle read by rows: T(n,k) is number of noncrossing trees with n edges and having k nonroot branch nodes.
%C Row n contains ceiling(n/2) terms.
%C Row sums yield the ternary numbers (A001764).
%C The average number of nonroot branch nodes over all noncrossing trees with n edges is 7n(n-1)(n-2)/(3(3n-1)(3n-2)) ~ 7n/27 (see A045737).
%H Andrew Howroyd, <a href="/A101431/b101431.txt">Table of n, a(n) for n = 1..930</a>
%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of non-crossing configurations</a>, Discrete Math., 204, 203-229, 1999.
%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, k) = (1/n)binomial(n, k)*Sum_{i=0..min(k, n-1-2k)} 3^(n-1-k-2i)*binomial(k, i)binomial(n-k, k+i+1), 0 <= k <= ceiling(n/2)-1.
%F G.f.: G=G(t, z) satisfies tzG^3 - (1 + 3tz - 3z)G + 1 + 2tz - 2z = 0.
%e T(2,0)=3 because /_, _\ and /\ have no nonroot branchnodes.
%e Triangle begins:
%e 1;
%e 3;
%e 9, 3;
%e 27, 28;
%e 81, 174, 18;
%e 243, 900, 285;
%e 729, 4185, 2703, 135;
%e ...
%p T:= proc(n,k) if k=0 then 3^(n-1) else (1/n)*binomial(n,k)*sum(3^(n-1-k-2*i)*binomial(k,i)*binomial(n-k,k+i+1),i=0..min(k,n-1-2*k)) fi end: for n from 1 to 12 do seq(T(n,k),k=0..ceil(n/2)-1) od; # yields sequence in triangular form
%t t[n_, k_] := (1/n)*Binomial[n, k]*Sum[3^(n - 1 - k - 2i)*Binomial[k, i]*Binomial[n - k, k + i + 1], {i, 0, Min[k, n - 1 - 2k]}]; Table[t[n, k], {n, 1, 12}, {k, 0, Ceiling[n/2] - 1}] // Flatten (* _Jean-François Alcover_, Jan 21 2013, after Maple *)
%o (PARI)
%o T(n,k)={binomial(n, k)*sum(i=0, min(k, n-1-2*k), 3^(n-1-k-2*i)*binomial(k, i)*binomial(n-k, k+i+1))/n}
%o for(n=1, 10, for(k=0, ceil(n/2)-1, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Nov 17 2017
%Y Cf. A001764, A045737.
%K nonn,tabf
%O 1,2
%A _Emeric Deutsch_, Jan 17 2005
|
