A087803 Number of unlabeled rooted trees with at most n nodes.

1, 2, 4, 8, 17, 37, 85, 200, 486, 1205, 3047, 7813, 20299, 53272, 141083, 376464, 1011311, 2732470, 7421146, 20247374, 55469206, 152524387, 420807242, 1164532226, 3231706871, 8991343381, 25075077710, 70082143979, 196268698287, 550695545884, 1547867058882

Offset

1,2

Comments

Number of equations (order conditions) that must be satisfied to achieve order n in the construction of a Runge-Kutta method for the numerical solution of an ordinary differential equation. - Hugo Pfoertner, Oct 12 2003

References

Butcher, J. C., The Numerical Analysis of Ordinary Differential Equations, (1987) Wiley, Chichester

See link for more references.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.

I. Th. Famelis, S. N. Papakostas and Ch. Tsitouras, Symbolic Derivation of Runge-Kutta Order Conditions.

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis (annotated cached copy).

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.

Florian Ingels, Revisiting Tree Isomorphism: AHU Algorithm with Primes Numbers, arXiv:2309.14441 [cs.DS], 2023. See p. 13.

Eric Weisstein's World of Mathematics, Rooted Tree.

Index entries for sequences related to rooted trees.

Formula

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.664861031240097088000569... . - Vaclav Kotesovec, Sep 11 2014

In the asymptotics above the constant c = A187770 / (1 - 1 / A051491). - Vladimir Reshetnikov, Aug 12 2016

Maple

with(numtheory):
b:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
a:= proc(n) option remember; b(n) +`if`(n<1, 0, a(n-1)) end:
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 21 2012

Mathematica

b[0] = 0; b[1] = 1; b[n_] := b[n] = Sum[b[n - j]* DivisorSum[j, # *b[#]&], {j, 1, n-1}]/(n-1); a[1] = 1; a[n_] := a[n] = b[n] + a[n-1]; Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Nov 10 2015, after Alois P. Heinz *)
t[1] = a[1] = 1; t[n_] := t[n] = Sum[k t[k] t[n - k m]/(n-1), {k, n}, {m, (n-1)/k}]; a[n_] := a[n] = a[n-1] + t[n]; Table[a[n], {n, 40}] (* Vladimir Reshetnikov, Aug 12 2016 *)
Needs["NumericalDifferentialEquationAnalysis`"]
Drop[Accumulate[Join[{0}, ButcherTreeCount[20]]], 1] (* Peter Luschny, Aug 18 2016 *)

Prog

(PARI) a000081(k) = local(A = x); if( k<1, 0, for( j=1, k-1, A /= (1 - x^j + x * O(x^k))^polcoeff(A, j)); polcoeff(A, k));
a(n) = sum(k=1, n, a000081(k)) \\ Altug Alkan, Nov 10 2015
(Sage)
def A087803_list(len):
    a, t = [1], [0, 1]
    for n in (1..len-1):
        S = [t[n-k+1]*sum(d*t[d] for d in divisors(k)) for k in (1..n)]
        t.append(sum(S)//n)
        a.append(a[-1]+t[-1])
    return a
A087803_list(20) # Peter Luschny, Aug 18 2016

Crossrefs

a(n) = Sum_(k=1..n) A000081(k).

Cf. A255170, A187770, A051491.

Sequence in context: A331783 A003426 A179476 * A212658 A036374 A214999

Adjacent sequences: A087800 A087801 A087802 * A087804 A087805 A087806

Keyword

nonn

Author

Hugo Pfoertner, Oct 12 2003

Extensions

Corrected and extended by Alois P. Heinz, Aug 21 2012.

Renamed (old name is in comments) by Vladimir Reshetnikov, Aug 23 2016.

Status

approved