login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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