login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004019 a(0) = 0; for n > 0, a(n) = (a(n-1) + 1)^2.
(Formerly M3611)
11
0, 1, 4, 25, 676, 458329, 210066388900, 44127887745906175987801, 1947270476915296449559703445493848930452791204, 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352025 (list; graph; refs; listen; history; text; internal format)
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..15

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fib. Quart., 11 (1973), 429-437.

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.

Index entries for sequences of form a(n+1)=a(n)^2 + ...

Index entries for sequences related to rooted trees

FORMULA

a(n) = A003095(n)^2 = A003095(n+1) - 1 = A056207(n+1) + 1.

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

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

Cf. A001699, A056207.

Cf. A000290.

Sequence in context: A167041 A123129 A075577 * A302092 A277110 A072882

Adjacent sequences:  A004016 A004017 A004018 * A004020 A004021 A004022

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

One more term from Henry Bottomley, Jul 24 2000

Additional comments from Max Alekseyev, Aug 30 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 19:18 EDT 2018. Contains 316530 sequences. (Running on oeis4.)