login
A101449
Triangle read by rows: T(n,k) is number of noncrossing trees with n edges and having k nonroot nodes of degree 1.
3
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
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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jan 17 2005
STATUS
approved