cp's OEIS Frontend

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.

%I A001699 M3087 N1251 #117 Jul 25 2025 12:01:12
%S A001699 1,1,3,21,651,457653,210065930571,44127887745696109598901,
%T A001699 1947270476915296449559659317606103024276803403,
%U A001699 3791862310265926082868235028027893277370233150300118107846437701158064808916492244872560821
%N 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.
%C A001699 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).
%D A001699 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
%D A001699 I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
%D A001699 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.
%D A001699 T. K. Moon, Enumerations of binary trees, types of trees and the number of reversible variable length codes, submitted to Discrete Applied Mathematics, 2000.
%D A001699 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001699 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%H A001699 David Wasserman, <a href="/A001699/b001699.txt">Table of n, a(n) for n = 0..12</a> [Shortened file because terms grow rapidly: see Wasserman link below for an additional term]
%H A001699 A. V. Aho and N. J. A. Sloane, <a href="https://web.archive.org/web/2024*/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.
%H A001699 A. V. Aho and N. J. A. Sloane, <a href="/A000058/a000058.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
%H A001699 Mayfawny Bergmann, <a href="http://scholar.rose-hulman.edu/rhumj/vol15/iss2/1/"> Efficiency of Lossless Compression of a Binary Tree via its Minimal Directed Acyclic Graph Representation</a>. Rose-Hulman Undergraduate Mathematics Journal: Vol. 15 : Iss. 2, Article 1. (2014).
%H A001699 Henry Bottomley, <a href="/A001699/a001699.gif">Illustration of initial terms</a>
%H A001699 I. M. H. Etherington, <a href="http://www.jstor.org/stable/3605743">Non-associate powers and a functional equation</a>, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
%H A001699 I. M. H. Etherington, <a href="/A000108/a000108_13.pdf">On non-associative combinations</a>, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]
%H A001699 Samuele Giraudo, <a href="https://arxiv.org/abs/2204.03586">The combinator M and the Mockingbird lattice</a>, arXiv:2204.03586 [math.CO], 2022.
%H A001699 Claude Lenormand, <a href="/A003095/a003095.pdf">Arbres et permutations II</a>, see p. 6
%H A001699 David E. Narváez, <a href="/A001699/a001699.pdf">Proof of polynomial recursive equation of order 2</a>, Jun 05 2025.
%H A001699 David Wasserman, <a href="/A001699/a001699.txt">Table of n, a(n) for n = 0..13</a>
%H A001699 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BinaryTree.html">Binary Tree</a>
%H A001699 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A001699 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A001699 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A001699 <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%H A001699 <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>
%F A001699 a(n+1) = 2*a(n)*(a(0) + ... + a(n-1)) + a(n)^2.
%F A001699 a(n+1) = a(n)^2 + a(n) + a(n)*sqrt(4*a(n)-3), if n > 0.
%F A001699 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
%F A001699 a(n) = A059826(A003095(n-1)).
%F A001699 From _Peter Bala_, Feb 03 2017: (Start)
%F A001699 a(n) = Product_{k = 1..n} A213437(k).
%F A001699 a(n) + a(n-1) = A213437(n+1) - A213437(n). (End)
%F A001699 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
%e A001699 G.f. = 1 + x + 3*x^2 + 21*x^3 + 651*x^4 + 457653*x^5 + ... - _Michael Somos_, Jun 02 2019
%p A001699 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);
%t A001699 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 *)
%t A001699 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 *)
%o A001699 (PARI) {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 */
%o A001699 (Python)
%o A001699 from functools import lru_cache
%o A001699 @lru_cache(maxsize=None)
%o A001699 def a(n): return 1 if n <= 1 else a(n-1) * (a(n-1) + a(n-2) + a(n-1)//a(n-2))
%o A001699 print([a(n) for n in range(10)]) # _Michael S. Branicky_, Nov 10 2022 after _Michael Somos_
%Y A001699 Row sums of A065329.
%Y A001699 Column sums of A335919, A335920.
%Y A001699 Cf. A002658, A056207, A002449, A003095.
%Y A001699 Cf. A004019, A077496, A076949, A213437.
%K A001699 nonn,easy,core,nice
%O A001699 0,3
%A A001699 _N. J. A. Sloane_ and _Jeffrey Shallit_
%E A001699 Minor edits by _Vaclav Kotesovec_, Oct 04 2014