|
| |
|
|
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.
|
|
7
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| 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
| Alois P. Heinz, Rows n = 1..141, flattened
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=1..12); # Alois P. Heinz, Sep 10 2008
|
|
|
MATHEMATICA
| f[list_]:=Select[list, #>0&]; Flatten[Map[f, Transpose[Table[t = Sum[n^(n - 2) x^n/n!, {n, 1, 20}]; Drop[Range[0, 8]! CoefficientList[Series[t^k/k!, {x, 0, 8}], x], 1], {k, 1, 8}]]]] (*Geoffrey Critzer, Nov 22 2011*)
|
|
|
CROSSREFS
| Cf. A033185, A106240.
Rows reflected give A138464. - Alois P. Heinz, Sep 10 2008
Sequence in context: A112292 A001497 A123244 * A106210 A033842 A104417
Adjacent sequences: A105596 A105597 A105598 * A105600 A105601 A105602
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Washington Bomfim (webonfim(AT)bol.com.br), Apr 14 2005; revised May 19 2005
|
| |
|
|
