A101449 Triangle read by rows: T(n,k) is number of noncrossing trees with n edges and having k nonroot nodes of degree 1.

1, 1, 2, 4, 4, 4, 11, 24, 12, 8, 41, 88, 96, 32, 16, 146, 410, 440, 320, 80, 32, 564, 1752, 2460, 1760, 960, 192, 64, 2199, 7896, 12264, 11480, 6160, 2688, 448, 128, 8835, 35184, 63168, 65408, 45920, 19712, 7168, 1024, 256, 35989, 159030, 316656, 379008

Offset

1,3

Comments

Row n contains n terms.

Row sums yield the ternary numbers (A001764).

The average number of nonroot nodes of degree 1 over all noncrossing trees with n edges is 4n(n-1)(2n+1)/(3(3n-1)(3n-2)) ~ 8n/27.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

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) = [2^k/(n-k)]*binomial(n-1, k)*Sum_{i=1..n-k} (-1)^(n-k-i)*2^(n-k-i)*binomial(n-k, i)*binomial(3i, i-1), 0 <= k < n).

T(n,k) = 2^k*binomial(n-1,k)*A030981(n-k).

Example

T(2,0)=1 (/\); T(2,1)=2 (/_, _\ ).
Triangle begins:
   1;
   1,  2;
   4,  4,  4;
  11, 24, 12,  8;
  41, 88, 96, 32, 16;

Maple

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

Mathematica

T[n_, k_] := If[k<n, 2^k*Binomial[n-1, k]*Sum[(-1)^(n-k-i)*2^(n-k-i)* Binomial[n-k, i]*Binomial[3*i, i-1], {i, 1, n-k}]/(n-k), 0];
Table[T[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jul 06 2018, from Maple *)

Prog

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

Crossrefs

Cf. A001764, A030981 (column 0).

Sequence in context: A260588 A107058 A332336 * A221564 A134188 A140295

Adjacent sequences: A101446 A101447 A101448 * A101450 A101451 A101452

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 17 2005

Status

approved