|
Search: id:A101452
|
|
|
| A101452 |
|
Triangle read by rows: T(n,k) is number of noncrossing trees with n edges and having k branches. |
|
+0
1
|
|
| 1, 2, 1, 4, 4, 4, 8, 12, 24, 11, 16, 32, 96, 88, 41, 32, 80, 320, 440, 410, 146, 64, 192, 960, 1760, 2460, 1752, 564, 128, 448, 2688, 6160, 11480, 12264, 7896, 2199, 256, 1024, 7168, 19712, 45920, 65408, 63168, 35184, 8835, 512, 2304, 18432, 59136, 165312
(list; table; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Mirror image of A101449. T(n,k)=2^(n-k)*binomial(n-1,k-1)*A030981(k). Row n contains n terms. Row sums yield the ternary numbers (A001764). T(n,n)=A030981(n) The average number of branchnodes over all noncrossing trees with n edges is n(n-1)(19n^2-23n+10)/[3(3n-1)(3n-2)] ~ 19n/27 (see A045738).
|
|
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^(n-k)/k]binomial(n-1, k-1)*sum((-2)^(k-i)*binomial(k, i)*binomial(3i, i-1), i=1..k). G.f.=G(t, z)=1/(1-F), where F satisfies F=z[t+2tF^2/(1-F)+tF^2/(1-F)^2+2F].
|
|
EXAMPLE
|
T(2,1)=2 because we have /_ and _\; T(2,2)=1 because we have /\
Triangle begins:
1;
2,1;
4,4,4;
8,12,24,11;
16,32,96,88,41;
|
|
MAPLE
|
T:=(n, k)->(2^(n-k)/k)*binomial(n-1, k-1)*sum((-2)^(k-i)*binomial(k, i)*binomial(3*i, i-1), i=1..k):for n from 1 to 10 do seq(T(n, k), k=1..n) od; #yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A001764, A030981, A045738.
Sequence in context: A111975 A117250 A136692 this_sequence A019963 A165417 A108755
Adjacent sequences: A101449 A101450 A101451 this_sequence A101453 A101454 A101455
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 19 2005
|
|
|
Search completed in 0.002 seconds
|
