login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A087803 Number of unlabeled rooted trees with at most n nodes. 17
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 (list; graph; refs; listen; history; text; internal format)
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.

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: A085022 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 18 18:07 EST 2018. Contains 318243 sequences. (Running on oeis4.)