|
%I M3087 N1251
%S 1,1,3,21,651,457653,210065930571,44127887745696109598901,
%T 1947270476915296449559659317606103024276803403,
%U 3791862310265926082868235028027893277370233150300118107846437701158064808916492244872560821
%N 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 Approaches 1.5028368...^(2^n). Row sums of A065329 as square array. - _Henry Bottomley_, Oct 29 2001. Also row sum of square array A073345 (AK).
%D I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
%D 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%H 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 A. V. Aho and N. J. A. Sloane, <a href="http://neilsloane.com/doc/doubly.html">Some doubly exponential sequences</a>, Fib. Quart., 11 (1973), 429-437.
%H H. Bottomley, <a href="/A001699/a001699.gif">Illustration of initial terms</a>
%H C. Lenormand, <a href="http://www.ai.univ-paris8.fr/~lenormand/I.2_Magmas_Arborescences.pdf">Arbres et permutations II</a>, see p. 6
%H David Wasserman, <a href="/A001699/a001699.txt">Table of n, a(n) for n = 0..13</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BinaryTree.html">Binary Tree</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%H <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>
%F a(n+1) = 2*a(n)*(a(0)+...+a(n-1))+a(n)^2.
%F a(n+1) = a(n)^2+a(n)+a(n)*sqrt(4*a(n)-3), if n>0.
%F a(n+1) = A003095(n+1)-A003095(n) = A003095(n)^2- A003095(n)+1. - _Henry Bottomley_, Apr 26 2001
%F a(n)=A059826(A003095(n-1))
%p 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 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 *)
%o (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 */
%Y Cf. A002658, A056207, A002449, A003095.
%Y Cf. A004019.
%K nonn,easy,core,nice
%O 0,3
%A _N. J. A. Sloane_, _Jeffrey Shallit_
| 