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,7

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.

Links

Alois P. Heinz, Rows n = 1..141, flattened

Eric Weisstein's World of Mathematics, Forest

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

Example

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.)

Crossrefs

Cf. A033185, A095133, A105786, A105821.

Sequence in context: A145677 A128229 A132013 * A136263 A105593 A029371

Adjacent sequences: A105817 A105818 A105819 * A105821 A105822 A105823

Keyword

nonn,tabl

Author

Washington Bomfim, Apr 25 2005

Status

approved