A274937 Number of unlabeled forests on n nodes that have exactly two nonempty components.

0, 0, 1, 1, 2, 3, 6, 11, 23, 46, 99, 216, 488, 1121, 2644, 6334, 15437, 38132, 95368, 241029, 614968, 1582030, 4100157, 10697038, 28075303, 74086468, 196470902, 523383136, 1400051585, 3759508536, 10131097618, 27391132238, 74283552343, 202030012554, 550934060120, 1506161266348

Offset: 0

Author

N. J. A. Sloane, Jul 19 2016

Keywords

• nonn

Links

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

Crossrefs

Cf. A000055, A274935, A274936, A274938. [A274935, A274936, A274937, A274938] are analogs for forests of [A275165, A275166, A216785, A274934] for graphs.

Programs

Maple

b:= proc(n) option remember; `if`(n<2, n, (add(add(d*
      b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
g:= proc(n) option remember; `if`(n=0, 1, b(n)-add(b(j)*
      b(n-j), j=0..n/2)+`if`(n::odd, 0, (t->t*(t+1)/2)(b(n/2))))
    end:
a:= proc(n) option remember; add(g(j)*g(n-j), j=1..n/2)-
      `if`(n::odd, 0, (t-> t*(t-1)/2)(g(n/2)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 20 2016

Mathematica

b[n_] := b[n] = If[n<2, n, Sum[DivisorSum[j, #*b[#]&]*b[n-j], {j, 1, n-1}]/ (n-1)];
g[n_] := g[n] = If[n==0, 1, b[n]-Sum[b[j]*b[n-j], {j, 0, n/2}] + If[OddQ[n], 0, Function[t, t*(t+1)/2][b[n/2]]]];
a[n_] := a[n] = Sum[g[j]*g[n-j], {j, 1, n/2}] - If[OddQ[n], 0, Function[t, t*(t-1)/2][g[n/2]]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 14 2017, after Alois P. Heinz *)

Formula

G.f.: [A(x)^2 + A(x^2)]/2 where A(x) is the o.g.f. for A000055 without the initial constant 1.

a(n) = A095133(n,2). - R. J. Mathar, Jul 20 2016