# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a002449 Showing 1-1 of 1 %I A002449 M1683 N0664 #67 Dec 12 2021 09:28:35 %S A002449 1,1,2,6,26,166,1626,25510,664666,29559718,2290267226,314039061414, %T A002449 77160820913242,34317392762489766,27859502236825957466, %U A002449 41575811106337540656038,114746581654195790543205466,588765612737696531880325270438,5642056933026209681424588087899226 %N A002449 Number of different types of binary trees of height n. %C A002449 Two trees have the same type if they have the same number of nodes at each level. - _Chams Lahlou_, Jan 26 2019 %C A002449 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 %D A002449 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. %D A002449 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. [From Don Knuth, Aug 17 2001.] %D A002449 R. F. Churchhouse, Congruence properties of the binary partition function. Proc. Cambridge Philos. Soc. 66 1969 371-376. %D A002449 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 A002449 D. E. Knuth, Selected Papers on Analysis of Algorithms, p. 75 (gives asymptotic formula and lower bound). %D A002449 H. Minc, The free commutative entropic logarithmetic. Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959). %D A002449 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. %D A002449 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). %D A002449 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %H A002449 T. D. Noe, Table of n, a(n) for n = 0..50 %H A002449 M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44. %H A002449 Chams Lahlou, A formula for some integer sequences that can be described by generating trees %F A002449 a(n) = A098539(n, 1). - _Paul D. Hanna_, Sep 13 2004 %F A002449 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 %F A002449 From _Benedict W. J. Irwin_, Nov 16 2016: (Start) %F A002449 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: %F A002449 a(3) = Sum_{i=1..2} 2*i. %F A002449 a(4) = Sum_{i=1..2}Sum_{j=1..2*i} 2*j. %F A002449 a(5) = Sum_{i=1..2}Sum_{j=1..2*i}Sum_{k=1..2*j} 2*k. %F A002449 (End) %F A002449 The conjecture is true: see Links. - _Chams Lahlou_, Jan 26 2019 %e A002449 G.f. = 1 + x + 2*x^2 + 6*x^3 + 26*x^4 + 166*x^5 + 1626*x^6 + 25510*x^7 + ... %p A002449 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 %t A002449 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_ *) %o A002449 (PARI) 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_ %o A002449 (PARI) a(n)=polcoeff(1/prod(k=0,n,1-x^(2^k)+O(x^(2^n))),2^n-1) %o A002449 (PARI) {a(n, k=2) = if(n<2, n>=0, sum(i=1, k, a(n-1, 2*i)))}; /* _Michael Somos_, Nov 24 2016 */ %Y A002449 Cf. A001699, A056207, A098539, A018819. %K A002449 nonn,nice,easy %O A002449 0,3 %A A002449 _N. J. A. Sloane_ %E A002449 Recurrence and more terms from _Michael Kleber_, Dec 05 2000 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE