Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #29 Dec 21 2023 18:51:38
%S 0,1,8,729,389017000,58871587162270593034051001,
%T 204040901322752673844230437877671861543858084850895762746141813554591014612008
%N a(0) = 0; a(n) = (1+a(n-1))^3 for n > 0.
%C Take the rooted ternary tree of depth n, with (3^(n+1) - 1) / 2 labeled nodes. Let the number of rooted subtrees be a(n). For example, for n = 1 the a(2) = 8 subtrees are:
%C R...R...R...R......R.......R...R.......R
%C .../....|....\..../.\...../|...|\...../|\
%C ..o.....o.....o..o...o...o.o...o.o...o.o.o
%C Then a(n+1) = (1+a(n))^3.
%H Geir Agnarsson, Elie Alhajjar, and Aleyah Dawkins, <a href="https://arxiv.org/abs/2312.11379">On locally finite ordered rooted trees and their rooted subtrees</a>, arXiv:2312.11379 [math.CO], 2023.
%H A. V. Aho and N. J. A. Sloane, <a href="https://www.fq.math.ca/Scanned/11-4/aho-a.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437, <a href="http://neilsloane.com/doc/doubly.html">alternative link</a>.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F As for A004019, it follows from Aho and Sloane that there is a constant c such that a(n) is the nearest integer to c^(3^n). In fact a(n) = nearest integer to b^(3^n) - 1 where b = 2.0804006677503193521177452323719035237099784935372250879749088464344434056773788...
%t {0}~Join~RecurrenceTable[{a[n]==(a[n-1]+1)^3, a[0]==1},a,{n,0,8}] (* _Vaclav Kotesovec_, May 21 2015 *)
%Y Cf. A000578, A004019, A368326, A368327.
%K easy,nonn
%O 0,3
%A _Paolo Bonzini_, Mar 15 2006; corrected Apr 06 2006 and Jan 19 2007
%E Name edited by _Michael De Vlieger_, Dec 21 2023