A038055 Number of n-node rooted trees with nodes of 2 colors.

2, 4, 14, 52, 214, 916, 4116, 18996, 89894, 433196, 2119904, 10503612, 52594476, 265713532, 1352796790, 6933598208, 35747017596, 185260197772, 964585369012, 5043220350012, 26467146038744, 139375369621960, 736229024863276, 3900074570513316, 20714056652990194

Offset: 1

Author

Christian G. Bower, Jan 04 1999

Keywords

• nonn
• eigen
• nice
• easy

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• L. Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA] (2018).
• R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Table 3.
• N. J. A. Sloane, Transforms
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Cf. A000081, A038056-A038062, A271878 (multisets).

Cf. A245870.

Programs

Maple

spec := [N, {N=Prod(bead,Set(N)), bead=Union(R,B), R=Atom, B=Atom}]; [seq(combstruct[count](spec, size=n), n=1..40)];
# second Maple program:
with(numtheory):
a:= proc(n) option remember; `if`(n<2, 2*n, (add(add(d*
      a(d), d=divisors(j))*a(n-j), j=1..n-1))/(n-1))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, May 11 2014

Mathematica

a[n_] := a[n] = If[n<2, 2*n, (Sum[Sum[d*a[d], {d, Divisors[j]}]*a[n-j], {j, 1, n-1}])/(n-1)]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)
a[1] = 2; a[n_] := a[n] = Sum[k a[k] a[n - m k]/(n-1), {k, n}, {m, (n-1)/k}]; Table[a[n], {n, 30}] (* Vladimir Reshetnikov, Aug 12 2016 *)

PARI

seq(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 2/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); 2*A} \\ Andrew Howroyd, May 12 2018

Formula

Shifts left and halves under Euler transform.

a(n) = 2*A000151(n).

a(n) ~ c * d^n / n^(3/2), where d = A245870 = 5.646542616232949712892713516..., c = 0.41572319484583484264330698410170337587070758092051645875080558178621559423... . - Vaclav Kotesovec, Sep 11 2014, updated Dec 26 2020