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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 16 01:36 EST 2017. Contains 296063 sequences.