|
%I #45 Oct 18 2023 12:22:55
%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 Florian Ingels, <a href="https://arxiv.org/abs/2309.14441">Revisiting Tree Isomorphism: AHU Algorithm with Primes Numbers</a>, arXiv:2309.14441 [cs.DS], 2023. See p. 13.
%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.
|
