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.

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

Offset: 0

Author

N. J. A. Sloane and Jeffrey Shallit

Keywords

• nonn
• easy
• core
• nice

Comments

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

Examples

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

References

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

Links

• 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 + ...

Crossrefs

Row sums of A065329.

Column sums of A335919, A335920.

Cf. A002658, A056207, A002449, A003095.

Cf. A004019, A077496, A076949, A213437.

Programs

Maple

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

Mathematica

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

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

Python

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

Formula

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

Extensions

Minor edits by Vaclav Kotesovec, Oct 04 2014