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

0, 1, 0, 2, 0, 0, 4, 1, 0, 0, 9, 2, 0, 0, 0, 20, 7, 1, 0, 0, 0, 48, 17, 2, 0, 0, 0, 0, 115, 48, 7, 1, 0, 0, 0, 0, 286, 124, 21, 2, 0, 0, 0, 0, 0, 719, 336, 60, 7, 1, 0, 0, 0, 0, 0, 1842, 888, 171, 21, 2, 0, 0, 0, 0, 0, 0, 4766, 2393, 488, 65, 7, 1, 0, 0, 0, 0, 0, 0

Offset: 1

Author

Washington Bomfim, Apr 26 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. A033185(n) = A106235(n) + A106234(n).

Examples

			a(12)=2 because 5 nodes can be partitioned in two trees only in a way: one tree gets 3 nodes and the other tree gets 2. Since A000081(3) = 2 and A000081(2)=1, there are two forests.
Triangle T(n,k) begins:
    0;
    1,   0;
    2,   0,  0;
    4,   1,  0, 0;
    9,   2,  0, 0, 0;
   20,   7,  1, 0, 0, 0;
   48,  17,  2, 0, 0, 0, 0;
  115,  48,  7, 1, 0, 0, 0, 0;
  286, 124, 21, 2, 0, 0, 0, 0, 0;
  719, 336, 60, 7, 1, 0, 0, 0, 0, 0;
		

Links

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

Crossrefs

Cf. A033185, A106234.

Programs

Maple

with(numtheory):
g:= proc(n) option remember; `if`(n<=1, n, (add(add(
      d*g(d), d=divisors(j))*g(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i=1,
      0, expand(add(x^j*b(n-i*j, i-1)*
      binomial(g(i)+j-1, j), j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, Jun 25 2014

Mathematica

g[n_] := g[n] = If[n <= 1, n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[n-j], {j, 1, n-1}])/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i == 1, 0, Expand[Sum[x^j*b[n-i*j, i-1]*Binomial[g[i]+j-1, j], {j, 0, n/i}]]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, n]]; Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Nov 05 2015, after Alois P. Heinz *)

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(A000081(i)+Ki-1, Ki).