A106236 Triangle of the numbers of different forests with m rooted trees having distinct orders.

1, 1, 0, 2, 1, 0, 4, 2, 0, 0, 9, 6, 0, 0, 0, 20, 13, 2, 0, 0, 0, 48, 37, 4, 0, 0, 0, 0, 115, 86, 17, 0, 0, 0, 0, 0, 286, 239, 46, 0, 0, 0, 0, 0, 0, 719, 577, 142, 8, 0, 0, 0, 0, 0, 0, 1842, 1607, 367, 18, 0, 0, 0, 0, 0, 0, 0, 4766, 4025, 1136, 76, 0, 0, 0, 0, 0, 0, 0, 0, 12486, 11185, 2945, 248, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset

1,4

Comments

a(n) = 0 if and only if n < m + (((1+m)*m - 1)^2 -1)/8, where m is the number of trees in the forests counted by a(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 distinct parts, of Product_{i=1..N}binomial(A000081(i)+Ki-1, Ki). Because all the multiplicities of the parts of the considered partitions are 1, or 0, we can simplify the formula to a(n)= sum over the partitions of N with exactly m distinct parts, of Product_{i=1..N}A000081(i). (Naturally, we do not consider the parts with multiplicity 0.)

G.f.: Product_{k>0} (1 + y*A000081(k)*x^k). - Vladeta Jovovic, May 14 2005

Example

a(3) = 0 because m = 2 and (see comments) 3 < (2 + 3).
a(4) > 0 because m = 1. Note that (((1+m)*m - 1)^2 -1)/8 = 0, if m = 1. It is clear that n >= m.

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..min(1, 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, Min[1, 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, Feb 23 2015, after Alois P. Heinz *)

Crossrefs

Cf. A000081, A106234.

Sequence in context: A166555 A136329 A122073 * A270640 A139136 A122792

Adjacent sequences: A106233 A106234 A106235 * A106237 A106238 A106239

Keyword

nonn,tabl

Author

Washington Bomfim, Apr 28 2005

Status

approved