A105820 Triangle giving the numbers of different forests of m trees of smallest order 2, i.e., without isolated vertices.

0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 3, 1, 0, 0, 0, 6, 3, 1, 0, 0, 0, 11, 5, 1, 0, 0, 0, 0, 23, 12, 3, 1, 0, 0, 0, 0, 47, 23, 6, 1, 0, 0, 0, 0, 0, 106, 52, 14, 3, 1, 0, 0, 0, 0, 0, 235, 110, 29, 6, 1, 0, 0, 0, 0, 0, 0, 551, 253, 68, 15, 3, 1, 0, 0, 0, 0, 0, 0, 1301, 570, 148, 31, 6, 1, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Author

Washington Bomfim, Apr 25 2005

Keywords

• nonn
• tabl

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.

Examples

			a(12) = 1 because 5 nodes can be partitioned into two trees only in one way: one tree gets 3 nodes and the other tree gets 2. Since A000055(3) = A000055(2) = 1, there is only one forest. (The forests of order less than or equal to 5 are depicted in the Weisstein link.)
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Eric Weisstein's World of Mathematics, Forest

Crossrefs

Cf. A033185, A095133, A105786, A105821.

Formula

a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m parts and no part equal to 1, of Product_{i=1..N} binomial(A000055(i)+Ki-1, Ki).

G.f.: 1/Product_{i>=2}(1 - x*y^i)^A000055(i). - Vladeta Jovovic, Apr 27 2005