A108521 Number of rooted trees with n generators.

1, 2, 5, 16, 53, 194, 730, 2868, 11526, 47370, 197786, 837467, 3585696, 15501423, 67563442, 296579626, 1309973823, 5817855174, 25964218471, 116379947718, 523699384013, 2364967753113, 10714396241046, 48684193997623

Offset

1,2

Comments

A generator is a leaf or a node with just one child.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

N. J. A. Sloane, Transforms

Eric Weisstein's World of Mathematics, Euler Transform.

Index entries for sequences related to rooted trees

Formula

G.f.: satisfies (2-x)*A(x) = x - 1 + EULER(A(x)).

Mathematica

a[1] = 1; a[n_] := a[n] = 1+a[n-1]+Total[Product[Binomial[a[i]-1+Count[#, i], Count[#, i]], {i, DeleteCases[DeleteDuplicates[#], 1]}]&/@ IntegerPartitions[n, {2, n-1}]]; Table[a[n], {n, 24}] (* Robert A. Russell, Jun 02 2020 *)
a[1] = 1; a[n_] := a[n] = a[n-1] + (DivisorSum[n, a[#] # &, #<n &] + Sum[c[k] b[n-k], {k, 1, n-1}])/n; b[n_] := b[n] = (c[n] + Sum[c[k] b[n-k], {k, 1, n-1}])/n; c[n_] := c[n] = DivisorSum[n, a[#] # &]; Table[a[k], {k, 24}] (* Robert A. Russell, Jun 04 2020 *)

Prog

(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(v=[1]); for(n=2, n, v=concat(v, v[#v] + EulerT(concat(v, [0]))[n])); v} \\ Andrew Howroyd, Aug 31 2018

Crossrefs

Cf. A000081, A000669, A007151, A108522 - A108529, A335342 (free trees).

Sequence in context: A149958 A148395 A148396 * A148397 A148398 A346518

Adjacent sequences: A108518 A108519 A108520 * A108522 A108523 A108524

Keyword

nonn

Author

Christian G. Bower, Jun 07 2005

Status

approved