|
| |
|
|
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, 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
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Row n contains n terms. Row sums yield the ternary numbers (A001764). Column 0 is A030981. T(n,k)=2^k*binomial(n-1,k)*A030981(n-k). 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.
|
|
|
REFERENCES
| P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 1999, 203-229.
M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math. 180, 1998, 301-313.
|
|
|
FORMULA
| T(n, k)=[2^k/(n-k)]*binomial(n-1, k)*sum((-1)^(n-k-i)*2^(n-k-i)*binomial(n-k, i)*binomial(3i, i-1), i=1..n-k) (0<=k<n).
|
|
|
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
|
|
|
CROSSREFS
| Cf. A001764, A030981.
Sequence in context: A021413 A082855 A107058 * A134188 A140295 A070529
Adjacent sequences: A101446 A101447 A101448 * A101450 A101451 A101452
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 17 2005
|
| |
|
|
