|
Search: id:A101431
|
|
|
| A101431 |
|
Triangle read by rows: T(n,k) is number of noncrossing trees with n edges and having k nonroot branchnodes. |
|
+0
1
|
|
| 1, 3, 9, 3, 27, 28, 81, 174, 18, 243, 900, 285, 729, 4185, 2703, 135, 2187, 18144, 19908, 3024, 6561, 74844, 125496, 38640, 1134, 19683, 297432, 711018, 369696, 32886, 59049, 1148175, 3725190, 2943090, 528930, 10206, 177147, 4330260, 18379548, 20588040, 6228585, 363528
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Row n contains ceil(n/2) terms. Row sums yield the ternary numbers (A001764). The average number of nonroot branchnodes over all noncrossing trees with n edges is 7n(n-1)(n-2)/[3(3n-1)(3n-2)] ~ 7n/27 (see A045737).
|
|
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)=(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)) (0<=k<=ceil(n/2)-1). G.f.=G=G(t, z) satisfies tzG^3-(1+3tz-3z)G+1+2tz-2z=0.
|
|
EXAMPLE
|
T(2,0)=3 because /_, _\, and /\ have no nonroot branchnodes.
Triangle begins:
1;
3;
9,3;
27,28;
81,174,18;
243,900,285;
|
|
MAPLE
|
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
|
|
CROSSREFS
|
Cf. A001764, A045737.
Sequence in context: A083996 A010259 A120429 this_sequence A120982 A125143 A130701
Adjacent sequences: A101428 A101429 A101430 this_sequence A101432 A101433 A101434
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 17 2005
|
|
|
Search completed in 0.002 seconds
|
