A339644 Number of rooted trees on n nodes with labels covering an initial interval of positive integers.

1, 3, 21, 214, 3004, 53696, 1169220, 30017582, 887835091, 29728120594, 1111619802614, 45914106227815, 2076062017348677, 101996651482313080, 5410363994433018486, 308174409706787225523, 18760485689929220881741, 1215547422537201878074293, 83520534389622385511232635

Offset

1,2

Links

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

Example

The a(3) = 21 rooted trees are:
  (1(11)), (1(1(1))), (1(12)), (1(22)), (1(1(2))), (1(2(1))), (1(2(2))), (2(12)), (2(11)), (2(2(1))), (2(1(2))), (2(1(1))), (1(23)), (1(2(3))), (1(3(2))), (2(13)), (2(1(3))), (2(3(1))), (3(12)), (3(1(2))), (3(2(1))).

Maple

b:= proc(n, k) option remember; `if`(n<2, k*n, (add(add(b(d, k)*
      d, d=numtheory[divisors](j))*b(n-j, k), j=1..n-1))/(n-1))
    end:
a:= n-> add(add(b(n, k-j)*binomial(k, j)*(-1)^j, j=0..k), k=0..n):
seq(a(n), n=1..21);  # Alois P. Heinz, Dec 11 2020

Mathematica

b[n_, k_] := b[n, k] = If[n<2, k*n, (Sum[Sum[b[d, k]*d, {d, Divisors[j]}]* b[n - j, k], {j, 1, n - 1}])/(n - 1)];
a[n_] := Sum[Sum[b[n, k - j]*Binomial[k, j]*(-1)^j, {j, 0, k}], {k, 0, n}];
Array[a, 21] (* Jean-François Alcover, Jan 04 2021, after Alois P. Heinz *)

Prog

(PARI) \\ See A141610 for U(n, k).
seq(n)={sum(k=1, n, U(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)))}

Crossrefs

Row sums of A141610.

Sequence in context: A087918 A088926 A291743 * A372159 A120972 A168479

Adjacent sequences: A339641 A339642 A339643 * A339645 A339646 A339647

Keyword

nonn

Author

Andrew Howroyd, Dec 11 2020

Status

approved