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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A087803 Number of unlabeled rooted trees with at most n nodes. 17

%I

%S 1,2,4,8,17,37,85,200,486,1205,3047,7813,20299,53272,141083,376464,

%T 1011311,2732470,7421146,20247374,55469206,152524387,420807242,

%U 1164532226,3231706871,8991343381,25075077710,70082143979,196268698287,550695545884,1547867058882

%N Number of unlabeled rooted trees with at most n nodes.

%C 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

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

%D See link for more references.

%H Alois P. Heinz, <a href="/A087803/b087803.txt">Table of n, a(n) for n = 1..1000</a>

%H A. Cayley, <a href="http://www.jstor.org/stable/2369158">On the analytical forms called trees</a>, Amer. J. Math., 4 (1881), 266-268.

%H I. Th. Famelis, S. N. Papakostas and Ch. Tsitouras, <a href="http://users.ntua.gr/tsitoura/SDRKOCfi.pdf">Symbolic Derivation of Runge-Kutta Order Conditions.</a>

%H R. K. Guy and J. L. Selfridge, <a href="/A003018/a003018.pdf">The nesting and roosting habits of the laddered parenthesis</a> (annotated cached copy).

%H R. K. Guy and J. L. Selfridge, <a href="http://www.jstor.org/stable/2319392">The nesting and roosting habits of the laddered parenthesis</a>, Amer. Math. Monthly 80 (8) (1973), 868-876.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RootedTree.html">Rooted Tree</a>.

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>.

%F a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.664861031240097088000569... . - _Vaclav Kotesovec_, Sep 11 2014

%F In the asymptotics above the constant c = A187770 / (1 - 1 / A051491). - _Vladimir Reshetnikov_, Aug 12 2016

%p with(numtheory):

%p b:= proc(n) option remember; local d, j; `if`(n<=1, n,

%p (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))

%p end:

%p a:= proc(n) option remember; b(n) +`if`(n<1, 0, a(n-1)) end:

%p seq(a(n), n=1..50); # _Alois P. Heinz_, Aug 21 2012

%t 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 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 *)

%t Needs["NumericalDifferentialEquationAnalysis`"]

%t Drop[Accumulate[Join[{0},ButcherTreeCount[20]]],1] (* _Peter Luschny_, Aug 18 2016 *)

%o (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));

%o a(n) = sum(k=1, n, a000081(k)) \\ _Altug Alkan_, Nov 10 2015

%o (Sage)

%o def A087803_list(len):

%o a, t = [1], [0,1]

%o for n in (1..len-1):

%o S = [t[n-k+1]*sum(d*t[d] for d in divisors(k)) for k in (1..n)]

%o t.append(sum(S)//n)

%o a.append(a[-1]+t[-1])

%o return a

%o A087803_list(20) # _Peter Luschny_, Aug 18 2016

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

%Y Cf. A255170, A187770, A051491.

%K nonn

%O 1,2

%A _Hugo Pfoertner_, Oct 12 2003

%E Corrected and extended by _Alois P. Heinz_, Aug 21 2012.

%E Renamed (old name is in comments) by _Vladimir Reshetnikov_, Aug 23 2016.

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 October 16 09:16 EDT 2018. Contains 316262 sequences. (Running on oeis4.)