login
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
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 giving only one vertex to a tree.
Also the Bell transform of A000272(n+1) (with a(0)=0). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016
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_{i=1..N}i^((i-2)Ki) and D = Product_{i=1..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 binomial(4,2) ways and to each one of the binomial(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 binomial(4,2) by 2!.
MAPLE
# The function BellMatrix is defined in A264428.
# Adds (1, 0, 0, 0, ..) as column 0.
BellMatrix(n -> `if`(n=0, 0, (n+1)^(n-1)), 9); # Peter Luschny, Jan 27 2016
MATHEMATICA
BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
B = BellMatrix[Function[n, If[n == 0, 0, (n+1)^(n-1)]], rows = 12];
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)
CROSSREFS
Sequence in context: A169777 A338464 A278208 * A291802 A221828 A368348
KEYWORD
nonn,tabl
AUTHOR
Washington Bomfim, Apr 21 2005
STATUS
approved