A174145 Number of rooted forests with n nodes in which each component contains at least two nodes.

1, 0, 1, 2, 5, 11, 28, 67, 171, 433, 1123, 2924, 7720, 20487, 54838, 147570, 399466, 1086312, 2967517, 8137552, 22395604, 61833349, 171227674, 475442129, 1323449661, 3692461865, 10324097819, 28923331940, 81179488039, 228240293289, 642744665401, 1812762839702

Offset: 0

Author

N. J. A. Sloane, Nov 26 2010

Keywords

• nonn

Comments

Row sums of A174135.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A000081, A051491, A187770, A255170.

Programs

Maple

with(numtheory):
t:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
      add(b(n-i*j, i-1)*binomial(t(i)+j-1, j), j=0..n/i)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..32);  # Alois P. Heinz, May 17 2013

Mathematica

t[n_] := t[n] = If[n <= 1, n, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<2, 0, Sum[b[n-i*j, i-1]*Binomial[t[i]+j-1, j], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n] // FullSimplify, {n, 0, 32}] (* Jean-François Alcover, Mar 19 2014, after Alois P. Heinz *)
t[1] = 1; t[n_] := t[n] = Sum[k t[k] t[n - k m]/(n-1), {k, n-1}, {m, (n-1)/k}]; a[n_] := t[n+1] - t[n]; Table[a[n], {n, 0, 32}] (* Vladimir Reshetnikov, Aug 12 2016 *)

Formula

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.8603881121111431... . - Vaclav Kotesovec, Sep 10 2014

In the asymptotics above the constant c = A187770 * (A051491 - 1). - Vladimir Reshetnikov, Aug 12 2016

a(n) = A000081(n+1) - A000081(n). - Vladimir Reshetnikov, Nov 06 2015