VOOZH about

URL: https://oeis.org/A087803

⇱ A087803 - OEIS

login
A087803
Number of unlabeled rooted trees with at most n nodes.
30
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
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: An Algorithmic Bric-à-Brac, arXiv:2309.14441 [cs.DS], 2023-2024. See p. 17.
Eric Weisstein's World of Mathematics, Rooted Tree.
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
(SageMath)
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).
Sequence in context: A331783 A003426 A179476 * A212658 A036374 A214999
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