A106237 Triangle of the numbers of different forests with m trees having distinct orders.
1, 1, 0, 1, 1, 0, 2, 1, 0, 0, 3, 3, 0, 0, 0, 6, 5, 1, 0, 0, 0, 11, 11, 2, 0, 0, 0, 0, 23, 20, 5, 0, 0, 0, 0, 0, 47, 46, 11, 0, 0, 0, 0, 0, 0, 106, 93, 26, 2, 0, 0, 0, 0, 0, 0, 235, 216, 58, 3, 0, 0, 0, 0, 0, 0, 0, 551, 467, 139, 12, 0, 0, 0, 0, 0, 0, 0, 0, 1301, 1121, 307, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0
Offset: 1
Examples
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.
Links
- Alois P. Heinz, Rows n = 1..141, flattened
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: h:= n-> `if`(n=0, 1, g(n) -(add(g(k) *g(n-k), k=0..n) -`if`(irem(n, 2)=0, g(n/2), 0))/2): 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(h(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)]; h[n_] := If[n == 0, 1, g[n] - (Sum[g[k]*g[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, g[n/2], 0])/2]; 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[h[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, Jan 28 2015, after Alois P. Heinz *)
Formula
a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m distinct parts, of Product_{i=1..N}binomial(A000055(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}A000055(i). (Naturally, we do not consider the parts with multiplicity 0.)
Comments