|
Search: id:A105786
|
|
|
| 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. |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
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: A011073 A104751 A123474 this_sequence A101192 A037288 A009133
Adjacent sequences: A105783 A105784 A105785 this_sequence A105787 A105788 A105789
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Washington Bomfim (webonfim(AT)bol.com.br), Apr 21 2005
|
|
|
Search completed in 0.002 seconds
|
