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

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

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

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

Prog

(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

Crossrefs

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

Cf. A245870.

Sequence in context: A316363 A295760 A129876 * A006385 A322859 A183949

Adjacent sequences: A038052 A038053 A038054 * A038056 A038057 A038058

Keyword

nonn,eigen,nice,easy

Author

Christian G. Bower, Jan 04 1999

Status

approved