A038060 Number of trees with 3-colored nodes.

1, 3, 6, 18, 75, 342, 1773, 9894, 58596, 362061, 2314119, 15185223, 101830986, 695253993, 4819762446, 33851833506, 240472935735, 1725315714729, 12487872432924, 91097741283408, 669227023979088, 4947500029023540, 36786363204267282, 274949933519917908

Offset: 0

Author

Christian G. Bower, Jan 04 1999

Keywords

• nonn

Links

• Index entries for sequences related to trees

Crossrefs

Cf. A000055, A038055-A038062.

Equals 3 * A006965(n).

Programs

Mathematica

b[n_] := b[n] = If[n < 2, 3n, (Sum[Sum[b[d] d, {d, Divisors[j]}] b[n - j], {j, 1, n - 1}])/(n - 1)];
a[n_] := If[n == 0, 1, b[n] - (Sum[b[k] b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2];
a /@ Range[0, 25] (* Jean-François Alcover, Nov 01 2020, after Alois P. Heinz in A006965 *)

Formula

G.f.: B(x) - B^2(x)/2 + B(x^2)/2, where B(x) is g.f. for A038059.