cp's OEIS Frontend

A087803 Number of unlabeled rooted trees with at most n nodes.

%I A087803 #53 May 08 2025 08:54:15
%S A087803 1,2,4,8,17,37,85,200,486,1205,3047,7813,20299,53272,141083,376464,
%T A087803 1011311,2732470,7421146,20247374,55469206,152524387,420807242,
%U A087803 1164532226,3231706871,8991343381,25075077710,70082143979,196268698287,550695545884,1547867058882
%N A087803 Number of unlabeled rooted trees with at most n nodes.
%C A087803 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 A087803 Butcher, J. C., The Numerical Analysis of Ordinary Differential Equations, (1987) Wiley, Chichester
%D A087803 See link for more references.
%H A087803 Alois P. Heinz, <a href="/A087803/b087803.txt">Table of n, a(n) for n = 1..1000</a>
%H A087803 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 A087803 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 A087803 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 A087803 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 A087803 Florian Ingels, <a href="https://arxiv.org/abs/2309.14441">Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac</a>, arXiv:2309.14441 [cs.DS], 2023-2024. See p. 17.
%H A087803 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RootedTree.html">Rooted Tree</a>.
%H A087803 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>.
%F A087803 a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.664861031240097088000569... . - _Vaclav Kotesovec_, Sep 11 2014
%F A087803 In the asymptotics above the constant c = A187770 / (1 - 1 / A051491). - _Vladimir Reshetnikov_, Aug 12 2016
%p A087803 with(numtheory):
%p A087803 b:= proc(n) option remember; local d, j; `if`(n<=1, n,
%p A087803       (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
%p A087803     end:
%p A087803 a:= proc(n) option remember; b(n) +`if`(n<1, 0, a(n-1)) end:
%p A087803 seq(a(n), n=1..50);  # _Alois P. Heinz_, Aug 21 2012
%t A087803 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 A087803 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 A087803 Needs["NumericalDifferentialEquationAnalysis`"]
%t A087803 Drop[Accumulate[Join[{0},ButcherTreeCount[20]]],1] (* _Peter Luschny_, Aug 18 2016 *)
%o A087803 (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 A087803 a(n) = sum(k=1, n, a000081(k)) \\ _Altug Alkan_, Nov 10 2015
%o A087803 (Sage)
%o A087803 def A087803_list(len):
%o A087803     a, t = [1], [0,1]
%o A087803     for n in (1..len-1):
%o A087803         S = [t[n-k+1]*sum(d*t[d] for d in divisors(k)) for k in (1..n)]
%o A087803         t.append(sum(S)//n)
%o A087803         a.append(a[-1]+t[-1])
%o A087803     return a
%o A087803 A087803_list(20) # _Peter Luschny_, Aug 18 2016
%Y A087803 a(n) = Sum_(k=1..n) A000081(k).
%Y A087803 Cf. A255170, A187770, A051491.
%K A087803 nonn
%O A087803 1,2
%A A087803 _Hugo Pfoertner_, Oct 12 2003
%E A087803 Corrected and extended by _Alois P. Heinz_, Aug 21 2012
%E A087803 Renamed (old name is in comments) by _Vladimir Reshetnikov_, Aug 23 2016