|
| |
|
|
A105819
|
|
Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e. without isolated vertices, on N labeled nodes.
|
|
0
|
|
|
|
0, 2, 0, 9, 0, 0, 64, 12, 0, 0, 625, 180, 0, 0, 0, 7776, 2730, 120, 0, 0, 0, 117649, 46410, 3780, 0, 0, 0, 0, 2097152, 893816, 99120, 1680, 0, 0, 0, 0, 43046721, 19389384, 2600640, 90720, 0, 0, 0, 0, 0, 1000000000, 469532790, 71734320, 3654000, 30240, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Forests of order N with m components, m > floor(N/2) must contain an isolated vertex since it is impossible to partition N vertices in floor(N/2) + 1 or more trees without give only one vertex to a tree.
|
|
|
LINKS
|
Table of n, a(n) for n=1..51.
|
|
|
FORMULA
|
a(n)= 0, if m > floor(N/2) (see comments), or can be calculated by the sum Num/D over the partitions of N:1K1+2K2+ ... + nKN, with exactly m parts and smallest part = 2, where Num = N!*product_{1=<i<=N}i^((i-1)Ki) and D = product_{1=<i<=N}(Ki!(i!)^Ki).
|
|
|
EXAMPLE
|
a(8) = 12 because 4 vertices can be partitioned in two trees only in one way: both trees receiving 2 vertices. Two trees on 2 vertices can be labeled in C(4, 2) manners and to each one of the 2C(4, 2) =12 possibilities there are more 2 possible trees of order 2 in a forest. But since we have 2 trees of the same order, i.e. 2, we must divide 2C(4,2)2 by 2!.
|
|
|
CROSSREFS
|
Cf. A033185, A105599.
Sequence in context: A193247 A091041 A140415 * A153616 A190258 A161119
Adjacent sequences: A105816 A105817 A105818 * A105820 A105821 A105822
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Washington Bomfim, Apr 21 2005
|
|
|
STATUS
|
approved
|
| |
|
|
