A056207 -id:A056207 - cp's OEIS frontend

A003095 a(n) = a(n-1)^2 + 1 for n >= 1, with a(0) = 0.

0, 1, 2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, 1947270476915296449559703445493848930452791205, 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352026

Offset: 0

N. J. A. Sloane and Richard Stanley

Number of binary trees of height less than or equal to n. [Corrected by Orson R. L. Peters, Jan 03 2020]
The rightmost digits cycle (0,1,2,5,6,7,0,1,2,5,6,7,...). - Jonathan Vos Post, Jul 21 2005
Apart from the initial term, a subsequence of A008318. - Reinhard Zumkeller, Jan 17 2008
Partial sums of A001699. - Jonathan Vos Post, Feb 17 2010
Corresponds to the second and second last diagonals of A119687. - John M. Campbell, Jul 25 2011
This is a divisibility sequence. - Michael Somos, Jan 01 2013
Sum_{n>=1} 1/a(n) = 1.739940825174794649210636285335916041018367182486941... . - Vaclav Kotesovec, Jan 30 2015
From Vladimir Vesic, Oct 03 2015: (Start)
Forming Herbrand's domains of formula: (∃x)(∀y)(∀z)(∃k)(P(x)∨Q(y)∧R(k))
where: x->a
       k->f(y,z)
we get:
  H0 = {a}
  H1 = {a, f(a,a)}
  H2 = {a, f(a,a), f(a,f(a,a)), f(f(a,a),a), f(f(a,a),f(a,a))}
  ...
The number of elements in each domain follows this sequence.
(End)
It is an open question whether or not this sequence satisfies Benford's law [Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
This is a strong divisibility sequence; see A329429. - Clark Kimberling, Nov 13 2019
From Peter Bala, Oct 31 2022: (Start)
Let k be a positive integer. Clearly, the sequence obtained by reducing a(n) modulo k is eventually periodic. Conjectures:
1) The sequence obtained by reducing a(n) modulo 2^k is eventually periodic with period 2.
2) The sequence obtained by reducing a(n) modulo 10^k is eventually periodic with period 6 (the case k = 1 is noted above).
3) The sequence obtained by reducing a(n) modulo 20^k is eventually periodic with period 6.
4) For n >= floor(k/2) and for 1 <= i <= 6, the value of a(6*n+i) mod 10^k is a constant independent of n. The digits of these 6 constant integers, when read from right to left, are the first k digits of the 10-adic numbers A318135 (i = 1), A318136 (i = 2), A318137 (i = 3), A318138 (i = 4), A318139 (i = 5) and A318140 (i = 6), respectively. An example is given below.
  n      a(6*n+1) mod 10^11
1           10066388901
2           72084948901
3           67988948901
4           61588948901
5           01588948901
6           01588948901
7           01588948901
...             ...
A318135 begins 1, 0, 9, 8, 4, 9, 8, 8, 5, 1, 0, 2, .... (End)

Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 443-448.
R. K. Guy, How to factor a number, Proc. 5th Manitoba Conf. Numerical Math., Congress. Num. 16 (1975), 49-89.
R. Penrose, The Emperor's New Mind, Oxford, 1989, p. 122.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..13
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
A. Berger and T. P. Hill, What is Benford's Law?, Notices, Amer. Math. Soc., 64:2 (2017), 132-134.
Neil J. Calkin, Eunice Y. S. Chan, and Robert M. Corless, Some Facts and Conjectures about Mandelbrot Polynomials, Maple Transactions (2021) Vol. 1, No. 1, Article 1.
P. Flajolet and A. M. Odlyzko, Limit distributions of coefficients of iterates of polynomials with applications to combinatorial enumerations, Math. Proc. Camb. Phil. Soc., 96 (1984), 237-253.
Claudio Gentile, Fabio Vitale, and Anand Rajagopalan, Flattening a Hierarchical Clustering through Active Learning, arXiv:1906.09458 [cs.LG], 2019.
Spencer Hamblen, Rafe Jones, and Kalyani Madhu, The density of primes in orbits of z^d + c, arXiv:1303.6513 [math.NT], 2013; to appear, Int. Math. Res. Not., c. 2015.
Dimitur Krustev, Simple Programs on Binary Trees Testing and Decidable Equivalence, 2016.
Robin Lamarche-Perrin, An Information-theoretic Framework for the Lossy Compression of Link Streams, arXiv:1807.06874 [cs.DS], 2018.
R. Lamarche-Perrin, Y. Demazeau, and J.-M. Vincent, A Generic Algorithmic Framework to Solve Special Versions of the Set Partitioning Problem, Preprint 105, Max-Planck-Institut fur Mathematik in den Naturwissenschaften, Leipzig, 2014.
C. Lenormand, Arbres et permutations II, see p. 6.
Saad Mneimneh, Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction, Department of Computer Science, Hunter College, CUNY, 2019.
Michael Penn, a stylish proof that..., YouTube video, 2021.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
M. Tainiter, Algebraic approach to stopping variable problems: Representation theory and applications, J. Combinatorial Theory 9 1970 148-161.
P. Tarau, A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.
Stephan Wagner and Volker Ziegler, Irrationality of growth constants associated with polynomial recursions, arXiv:2004.09353 [math.NT], 2020.
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 to divisibility sequences
Index entries for sequences related to Benford's law

Cf. A001699, A004019, A038044, A056207, A076949, A077496, A091980, A143848.
Cf. A143849, A213437, A247981, A248218, A248219, A318135, A318136, A318137.
Cf. A318138, A318139, A318140, A355108.
Cf. A137560, which enumerates binary trees of height less than n and exactly j leaf nodes. - Robert Munafo, Nov 03 2009

function A003095(n)
  if n eq 0 then return 0;
  else return 1 + A003095(n-1)^2;
  end if; return A003095;
end function;
[A003095(n): n in [0..12]]; // G. C. Greubel, Nov 29 2022

a:= proc(n) option remember; `if`(n=0, 0, a(n-1)^2+1) end:
seq(a(n), n=0..10);  # Alois P. Heinz, Jul 11 2019

NestList[#^2+1&,0,10] (* Harvey P. Dale, Dec 17 2010 *)

{a(n) = if( n<1, 0, 1 + a(n-1)^2)}; /* Michael Somos, Jan 01 2013 */

def A003095(n): return 0 if (n==0) else 1 + A003095(n-1)^2
[A003095(n) for n in range(13)] # G. C. Greubel, Nov 29 2022

a(n) = B_{n-1}(1) where B_n(x) = 1 + x*B_{n-1}(x)^2 is the generating function of trees of height <= n.
a(n) is asymptotic to c^(2^n) where c=1.2259024435287485386279474959130085213... (see A076949). - Benoit Cloitre, Nov 27 2002
c = b^(1/4) where b is the constant in Bottomley's formula in A004019. a(n) appears very asymptotic to c^(2^n) - Sum_{k>=1} A088674(k)/(2*c^(2^n))^(2*k-1). - Gerald McGarvey, Nov 17 2007
a(n) = Sum_{i=1..n} A001699(i). - Jonathan Vos Post, Feb 17 2010
G.f. = x + 2*x^2 + 5*x^3 + 26*x^4 + 677*x^5 + 458330*x^6 + 210066388901*x^7 + ... . - Michael Somos, Jan 01 2013
a(2n) mod 2 = 0 ; a(2n+1) mod 2 = 1. - Altug Alkan, Oct 04 2015
a(n) + a(n-1) = A213437(n). - Peter Bala, Feb 03 2017
0 = a(n)^2*(+a(n+1) + a(n+2)) + a(n+1)^2*(-a(n+1) - a(n+2) - a(n+3)) + a(n+2)^3 for all n>=0. - Michael Somos, Feb 10 2017
a(n) = A091980(2^(n-1)) for n > 0. - Alois P. Heinz, Jul 11 2019

Additional comments from Cyril Banderier, Jun 05 2000
Minor edits by Vaclav Kotesovec, Oct 04 2014
Initial term clarified by Clark Kimberling, Nov 13 2019

A001699 Number of binary trees of height n; or products (ways to insert parentheses) of height n when multiplication is non-commutative and non-associative.

Original entry on oeis.org

1, 1, 3, 21, 651, 457653, 210065930571, 44127887745696109598901, 1947270476915296449559659317606103024276803403, 3791862310265926082868235028027893277370233150300118107846437701158064808916492244872560821

Offset: 0

N. J. A. Sloane and Jeffrey Shallit

Approaches 1.5028368...^(2^n), see A077496. Row sums of A065329 as square array. - Henry Bottomley, Oct 29 2001. Also row sum of square array A073345 (AK).

			G.f. = 1 + x + 3*x^2 + 21*x^3 + 651*x^4 + 457653*x^5 + ... - _Michael Somos_, Jun 02 2019

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
T. K. Moon, Enumerations of binary trees, types of trees and the number of reversible variable length codes, submitted to Discrete Applied Mathematics, 2000.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

David Wasserman, Table of n, a(n) for n = 0..12 [Shortened file because terms grow rapidly: see Wasserman link below for an additional term]
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
Mayfawny Bergmann, Efficiency of Lossless Compression of a Binary Tree via its Minimal Directed Acyclic Graph Representation. Rose-Hulman Undergraduate Mathematics Journal: Vol. 15 : Iss. 2, Article 1. (2014).
Henry Bottomley, Illustration of initial terms
I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]
Samuele Giraudo, The combinator M and the Mockingbird lattice, arXiv:2204.03586 [math.CO], 2022.
Claude Lenormand, Arbres et permutations II, see p. 6
David E. Narváez, Proof of polynomial recursive equation of order 2, Jun 05 2025.
David Wasserman, Table of n, a(n) for n = 0..13
Eric Weisstein's World of Mathematics, Binary Tree
Index entries for "core" sequences
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
Index entries for sequences related to parenthesizing
Index entries for sequences of form a(n+1)=a(n)^2 + ...

Row sums of A065329.
Column sums of A335919, A335920.
Cf. A002658, A056207, A002449, A003095.
Cf. A004019, A077496, A076949, A213437.

s := proc(n) local i,j,ans; ans := [ 1 ]; for i to n do ans := [ op(ans),2*(add(j,j=ans)-ans[ i ])*ans[ i ]+ans[ i ]^2 ] od; RETURN(ans); end; s(10);

a[0] = 1; a[n_] := a[n] = 2*a[n-1]*Sum[a[k], {k, 0, n-2}] + a[n-1]^2; Table[a[n], {n, 0, 9}] (* Jean-François Alcover, May 16 2012 *)
a[ n_] := If[ n < 2, Boole[n >= 0], With[{u = a[n - 1], v = a[n - 2]}, u (u + v + u/v)]]; (* Michael Somos, Jun 02 2019 *)

{a(n) = if( n<=1, n>=0, a(n-1) * (a(n-1) + a(n-2) + a(n-1) / a(n-2)))}; /* Michael Somos, 2000 */

from functools import lru_cache
@lru_cache(maxsize=None)
def a(n): return 1 if n <= 1 else a(n-1) * (a(n-1) + a(n-2) + a(n-1)//a(n-2))
print([a(n) for n in range(10)]) # Michael S. Branicky, Nov 10 2022 after Michael Somos

a(n+1) = 2*a(n)*(a(0) + ... + a(n-1)) + a(n)^2.
a(n+1) = a(n)^2 + a(n) + a(n)*sqrt(4*a(n)-3), if n > 0.
a(n) = A003095(n+1) - A003095(n) = A003095(n)^2 - A003095(n) + 1. - Henry Bottomley, Apr 26 2001; offset of LHS corrected by Anindya Bhattacharyya, Jun 21 2013
a(n) = A059826(A003095(n-1)).
From Peter Bala, Feb 03 2017: (Start)
a(n) = Product_{k = 1..n} A213437(k).
a(n) + a(n-1) = A213437(n+1) - A213437(n). (End)
a(n) = -a(n-2)^3 + a(n-1)^2 + 3*a(n-1)*a(n-2) + 2*a(n-2)^2 + 2*a(n-1) - 4*a(n-2) (see Narváez link for proof). - Boštjan Gec, Oct 10 2024

Minor edits by Vaclav Kotesovec, Oct 04 2014

A004019 a(0) = 0; for n > 0, a(n) = (a(n-1) + 1)^2.

Original entry on oeis.org

0, 1, 4, 25, 676, 458329, 210066388900, 44127887745906175987801, 1947270476915296449559703445493848930452791204, 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352025

Offset: 0

N. J. A. Sloane

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).

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.

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.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
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.
E. Lappo and N. A. Rosenberg, A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees, Adv. Appl. Math. 343 (2024), 65-81.
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

Cf. A001699, A056207.
Cf. A000290.
Cf. A003095, A091980, A355108.

a004019 n = a004019_list !! n
a004019_list = iterate (a000290 . (+ 1)) 0
-- Reinhard Zumkeller, Feb 01 2013

[n le 1 select 0 else  (Self(n-1)+1)^2: n in [1..15]]; // Vincenzo Librandi, Oct 05 2015

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 *)

a(n) = if(n==0, 0, (a(n-1) + 1)^2);
vector(20, n, a(n-1)) \\ Altug Alkan, Oct 06 2015

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
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

One more term from Henry Bottomley, Jul 24 2000

Additional comments from Max Alekseyev, Aug 30 2005

A002449 Number of different types of binary trees of height n.

Original entry on oeis.org

1, 1, 2, 6, 26, 166, 1626, 25510, 664666, 29559718, 2290267226, 314039061414, 77160820913242, 34317392762489766, 27859502236825957466, 41575811106337540656038, 114746581654195790543205466, 588765612737696531880325270438, 5642056933026209681424588087899226

Offset: 0

N. J. A. Sloane

Two trees have the same type if they have the same number of nodes at each level. - Chams Lahlou, Jan 26 2019

Equals the number of partitions of 2^n-1 into powers of 2 (cf. A018819). a(n) = A018819(2^n-1) = binary partitions of 2^n-1. - Paul D. Hanna, Sep 22 2004

			G.f. = 1 + x + 2*x^2 + 6*x^3 + 26*x^4 + 166*x^5 + 1626*x^6 + 25510*x^7 + ...

George E. Andrews, Peter Paule, Axel Riese and Volker Strehl, "MacMahon's Partition Analysis V: Bijections, recursions and magic squares," in Algebraic Combinatorics and Applications, edited by Anton Betten, Axel Kohnert, Reinhard Laue and Alfred Wassermann [Proceedings of ALCOMA, September 1999] (Springer, 2001), 1-39.
A. Cayley, "On a problem in the partition of numbers," Philosophical Magazine (4) 13 (1857), 245-248; reprinted in his Collected Math. Papers, Vol. 3, pp. 247-249. - Don Knuth, Aug 17 2001
R. F. Churchhouse, Congruence properties of the binary partition function. Proc. Cambridge Philos. Soc. 66 1969 371-376.
R. F. Churchhouse, Binary partitions, pp. 397-400 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
D. E. Knuth, Selected Papers on Analysis of Algorithms, p. 75 (gives asymptotic formula and lower bound).
H. Minc, The free commutative entropic logarithmetic. Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).
T. K. Moon (tmoon(AT)artemis.ece.usu.edu), Enumerations of binary trees, types of trees and the number of reversible variable length codes, submitted to Discrete Applied Mathematics, 2000.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..50
A. Cayley, On a problem in the partition of numbers, Philosophical Magazine (4) 13 (1857), 245-248; reprinted in his Collected Math. Papers, Vol. 3, pp. 247-249.
M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.
Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See pp. 31, 33, 34.
Chams Lahlou, A formula for some integer sequences that can be described by generating trees

Cf. A001699, A056207, A098539, A018819.

d := proc(n) option remember; if n<1 then 1 else sum(d(n-1),k=1..2*k) fi end; A002449 := n -> eval(d(n-1),k=1); # Michael Kleber, Dec 05 2000

lim = 16; p[0] = p[1] = 1; Do[If[OddQ[n], p[n] = p[n - 1], p[n] = p[n - 1] + p[n/2]], {n, 1, 2^lim - 1}]; a[n_] := p[2^n - 1]; Table[a[n], {n, 0, lim}] (* Jean-François Alcover, Sep 20 2011, after Paul D. Hanna *)

a(n)=local(A,B,C,m);A=matrix(1,1);A[1,1]=1; for(m=2,n+1,B=A^2;C=matrix(m,m);for(j=1,m, for(k=1,j, if(j<3 || k==j || k>m-1,C[j,k]=1,if(k==1,C[j,k]=B[j-1,1],C[j,k]=B[j-1,k-1])); ));A=C);A[n+1,1] \\ Paul D. Hanna

a(n)=polcoeff(1/prod(k=0,n,1-x^(2^k)+O(x^(2^n))),2^n-1)

{a(n, k=2) = if(n<2, n>=0, sum(i=1, k, a(n-1, 2*i)))}; /* Michael Somos, Nov 24 2016 */

a(n) = A098539(n, 1). - Paul D. Hanna, Sep 13 2004
G.f. A(x) = F(x,1) where F(x,n) satisfies: F(x,n) = F(x,n-1) + xF(x,2n) for n>0 with F(x,0)=1. - Paul D. Hanna, Apr 16 2007
From Benedict W. J. Irwin, Nov 16 2016: (Start)
Conjecture: a(n+2) = Sum_{i_1=1..2}Sum_{i_2=1..2*i_1}...Sum_{i_n=1..2*i_(n-1)} (2*i_n). For example:
a(3) = Sum_{i=1..2} 2*i.
a(4) = Sum_{i=1..2}Sum_{j=1..2*i} 2*j.
a(5) = Sum_{i=1..2}Sum_{j=1..2*i}Sum_{k=1..2*j} 2*k. (End)
The conjecture is true: see Links. - Chams Lahlou, Jan 26 2019

Recurrence and more terms from Michael Kleber, Dec 05 2000

A060137 Square array read by antidiagonals with T(n,k)=T(n,k-1)^2-n*T(n,k-1)+1 and T(n,0)=0.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 5, 1, 1, 0, 26, 1, 0, 1, 0, 677, 1, 1, -1, 1, 0, 458330, 1, 0, 5, -2, 1, 0, 210066388901, 1, 1, 11, 13, -3, 1, 0, 44127887745906175987802, 1, 0, 89, 118, 25, -4, 1, 0, 1947270476915296449559703445493848930452791205, 1, 1, 7655, 13453, 501, 41, -5, 1, 0

Offset: 0

Henry Bottomley, Mar 05 2001

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

Rows include A003095, A057427, A000035. Columns include A000004, A000012, A022958, A001844 (offset). Cf. A060136.

T(0,k)=A004019(k-1)+1=A056207(k-2)+2. - R. J. Mathar, Apr 24 2007

A367433 Number of successive Patcail predecessors of n-th binary tree.

Original entry on oeis.org

0, 1, 2, 5, 3, 6, 4

Offset: 0

John Tromp, Nov 18 2023

nonn

A binary tree is either 0 or a pair [s,t] of binary trees. Binary trees are counted by Catalan numbers A000108 and ordered by their binary code as given by A014486. Subtrees s and t correspond to A072771 and A072772.
Patcail defined the predecessor of [0,t] as t, and of [s,t], where s has predecessor s', as the result of replacing with [s',t] each occurrence of t within [s',t].
a(7), corresponding to [[0,[0,0]],0], is too large to show, exceeding an exponential tower of 2^63 2's. a(8), corresponding to [[[0,0],0],0], is much larger still, starting to approach Graham's Number. The next 3 terms are modest again, at a(9)=4, a(10)=7, a(11)=5.
The (A014138 indexed) subsequence for left skewed binary trees 0, [0,0], [[0,0],0], [[[0,0],0],0] ... forms an extremely fast growing sequence, at Buchholz's Ordinal in the Fast Growing Hierarchy.
Initial predecessors of these left skewed trees have sizes a(n) satisfying
a(n+1) = (a(n)+1)*(a(n)+3), which is A056207 counting the number of binary trees of height <= n.

			a(3)=5, since the 3rd binary tree is [[0,0],0] and its 5 successive Patcail predecessors are [[0,0],[0,0]], [0,[0,[0,0]]], [0,[0,0]], [0,0], and 0:
Index   n         3              6              4          2      1   0
A014486(n)       12             50             42         10      2   0
A063171(n)     1100         110010         101010       1010     10   0
Tree       [[0,0],0]  [[0,0],[0,0]]  [0,[0,[0,0]]]  [0,[0,0]]  [0,0]  0
A367433(n)        5              4              3          2      1   0

Code Golf, Patcail's winning answer to Code Golf challenge "Golf a number bigger than TREE(3)".

Cf. A000108, A014486, A014138, A056207.

data T = N | C T T deriving (Eq,Show)
a014486 = [0..] >>= at where
  at 0 = [N]
  at n = [C s t | (ns,s) <- to$n-1, t <- at$n-1-ns]
  to n = (0,N):[(1+ns+nt,C s t)|n>0,(ns,s)<-to$n-1,(nt,t)<-to$n-1-ns]
predT (C N t) = t
predT (C s t) = go u where
  u = [predT s) t
  go v = if v==t then u else case v of
    N     -> N
    C s t -> [go s) (go t)
a367433 = map nPred a014486 where
  nPred N = 0
  nPred t = 1 + nPred (predT t)

cp's OEIS Frontend

A003095 a(n) = a(n-1)^2 + 1 for n >= 1, with a(0) = 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A001699 Number of binary trees of height n; or products (ways to insert parentheses) of height n when multiplication is non-commutative and non-associative.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A004019 a(0) = 0; for n > 0, a(n) = (a(n-1) + 1)^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

Extensions

A002449 Number of different types of binary trees of height n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A060137 Square array read by antidiagonals with T(n,k)=T(n,k-1)^2-n*T(n,k-1)+1 and T(n,0)=0.

Views

Author

Keywords

Links

Crossrefs

Formula

A367433 Number of successive Patcail predecessors of n-th binary tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs