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,5

Links

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

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

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

Crossrefs

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

Sequence in context: A036592 A036656 A001190 * A359392 A199142 A090344

Adjacent sequences: A274934 A274935 A274936 * A274938 A274939 A274940

Keyword

nonn

Author

N. J. A. Sloane, Jul 19 2016

Status

approved