OFFSET
0,3
COMMENTS
Take the standard rooted binary tree of depth n, with 2^(n+1) - 1 labeled nodes. Here is a picture of the tree of depth 3:
R
/ \
/ \
/ \
/ \
/ \
o o
/ \ / \
/ \ / \
o o o o
/ \ / \ / \ / \
o o o o o o o o
Let the number of rooted subtrees be s(n). For example, for n = 1 the s(2) = 4 subtrees are:
R R R R
/ \ / \
o o o o
Then s(n+1) = 1 + 2*s(n) + s(n)^2 = (1+s(n))^2 and so s(n) = a(n+1).
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203.
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..11 (shortened by N. J. A. Sloane, Jan 13 2019)
Geir Agnarsson, Elie Alhajjar, and Aleyah Dawkins, On locally finite ordered rooted trees and their rooted subtrees, arXiv:2312.11379 [math.CO], 2023.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437, alternative link.
Andressa Paola Cordeiro, Alexandre Tavares Baraviera, and Alex Jenaro Becker, Entropy for k-trees defined by k transition matrices, arXiv:2307.05850 [math.DS], 2023. See p. 15.
F. Disanto and N. A. Rosenberg, Enumeration of ancestral configurations for matching gene trees and species trees, J. Comput. Biol. 24 (2017), 831-850.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
Elmar Teufl and Stephan Wagner, Enumeration problems for classes of self-similar graphs, Journal of Combinatorial Theory, Series A, Volume 114, Issue 7, October 2007, Pages 1254-1277.
Wikipedia, Herbrand Structure
Damiano Zanardini, Computational Logic, UPM European Master in Computational Logic (EMCL) School of Computer Science Technical University of Madrid.
FORMULA
It follows from Aho and Sloane that there is a constant c such that a(n) is the nearest integer to c^(2^n). In fact a(n+1) = nearest integer to b^(2^n) - 1 where b = 2.25851845058946539883779624006373187243427469718511465966.... - Henry Bottomley, Aug 30 2005
a(n) is the number of root ancestral configurations for fully symmetric matching gene trees and species trees with 2^n leaves, a(n) = A355108(2^n). - Noah A Rosenberg, Jun 22 2022
MATHEMATICA
Table[Nest[(1 + #)^2 &, 0, n], {n, 0, 12}] (* Vladimir Joseph Stephan Orlovsky, Jul 20 2011 *)
NestList[(#+1)^2&, 0, 10] (* Harvey P. Dale, Oct 08 2011 *)
PROG
(Haskell)
a004019 n = a004019_list !! n
a004019_list = iterate (a000290 . (+ 1)) 0
-- Reinhard Zumkeller, Feb 01 2013
(Magma) [n le 1 select 0 else (Self(n-1)+1)^2: n in [1..15]]; // Vincenzo Librandi, Oct 05 2015
(PARI) a(n) = if(n==0, 0, (a(n-1) + 1)^2);
vector(20, n, a(n-1)) \\ Altug Alkan, Oct 06 2015
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
One more term from Henry Bottomley, Jul 24 2000
Additional comments from Max Alekseyev, Aug 30 2005
STATUS
approved