|
| |
|
|
A105786
|
|
Triangle of the numbers of different forests of m unrooted trees of smallest order 2, i.e. without isolated vertices, on N labeled nodes.
|
|
1
| |
|
|
0, 1, 0, 3, 0, 0, 16, 3, 0, 0, 125, 30, 0, 0, 0, 1296, 330, 15, 0, 0, 0, 16807, 4305, 315, 0, 0, 0, 0, 262144, 66248, 5880, 105, 0, 0, 0, 0, 4782969, 1183644, 115290, 3780, 0, 0, 0, 0, 0, 100000000, 24170310, 2467080, 107100, 945, 0, 0, 0, 0, 0, 2357947691, 556409535
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
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.
|
|
|
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-2)Ki) and D = product_{1=<i<=N}(Ki!(i!)^Ki).
|
|
|
EXAMPLE
| a(8) = 3 because 4 vertices can be partitioned in two trees only in one way: both trees receiving 2 vertices. The unique tree on 2 vertices can be labeled in C(4, 2) manners and to each one of the C(4, 2) = 6 possibilities there is just another tree of order 2 in a forest. But since we have 2 trees of the same order, i.e. 2, we must divide C(4,2) by 2!.
|
|
|
CROSSREFS
| Cf. A033185, A105599.
Sequence in context: A177016 A123474 A169777 * A101192 A037288 A160537
Adjacent sequences: A105783 A105784 A105785 * A105787 A105788 A105789
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Washington Bomfim (webonfim(AT)bol.com.br), Apr 21 2005
|
| |
|
|
