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

Links

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

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

Example

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;

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

Crossrefs

Cf. A033185, A106234.

Sequence in context: A136334 A155039 A238858 * A288098 A118965 A252729

Adjacent sequences: A106232 A106233 A106234 * A106236 A106237 A106238

Keyword

nonn,tabl

Author

Washington Bomfim, Apr 26 2005

Status

approved