|
Search: id:A105599
|
|
|
| A105599 |
|
Triangle read by rows: T(n, m) = number of forests with n nodes and m labeled trees. Also number of forests with exactly n - m edges on n labeled nodes. |
|
+0
6
|
|
| 1, 1, 1, 3, 3, 1, 16, 15, 6, 1, 125, 110, 45, 10, 1, 1296, 1080, 435, 105, 15, 1, 16807, 13377, 5250, 1295, 210, 21, 1, 262144, 200704, 76608, 18865, 3220, 378, 28, 1, 4782969, 3542940, 1316574, 320544, 55755, 7056, 630, 36, 1, 100000000, 72000000
(list; table; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
Row sums equal A001858 (number of forests of labeled trees with n nodes).
T(n,m) = Sum_{k=1..n-m+1} binomial(n-1,k-1)*k^(k-2)*T(n-k,m-1), T(n,0) = 0 if n>0, T(0,0) = 1. Vladeta Jovovic (vladeta(AT)eunet.rs) and Washington Bomfim (webonfim(AT)bol.com.br).
|
|
REFERENCES
|
B. Bollobas, Graph Theory - An Introductory Course (Springer-Verlag, New York, 1979)
|
|
LINKS
|
Washington Bomfim, Illustration Of This Sequence.
|
|
FORMULA
|
The value of T(n, m) can be calculated by the formula in Bollobas, pp. 172, exercise 44. Also T(n, m)= sum N/D over the partitions of n, 1*K(1) + 2*K(2) + ... + n*K(n), with exactly m parts, where N = n! * product_{i = 1..n} i^( (i-2) * K(i) ) and D = product_{i = 1..n} ( K(i)! * (i!)^K(i) ).
|
|
EXAMPLE
|
T(3, 2) = 3 because there are 3 such forests with 3 nodes and 2 trees.
Triangle begins:
1,
1, 1,
3, 3, 1,
16, 15, 6, 1,
125, 110, 45, 10, 1,
1296, 1080, 435, 105, 15, 1,
16807, 13377, 5250, 1295, 210, 21, 1,
|
|
MAPLE
|
T:= proc(n, m) option remember; if n<0 then 0 elif n=m then 1 elif m<1 or m>n then 0 else add (binomial (n-1, j-1) *j^(j-2) *T(n-j, m-1), j=1..n-m+1) fi end: seq (seq (T(n, m), m=1..n), n=0..12); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 10 2008]
|
|
CROSSREFS
|
Cf. A033185, A106240.
Rows reflected give A138464. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 10 2008]
Sequence in context: A112292 A001497 A123244 this_sequence A106210 A033842 A104417
Adjacent sequences: A105596 A105597 A105598 this_sequence A105600 A105601 A105602
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Washington Bomfim (webonfim(AT)bol.com.br), Apr 14 2005; revised May 19 2005
|
|
|
Search completed in 0.002 seconds
|
