cp's OEIS Frontend

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

%I A002449 M1683 N0664 #77 Aug 24 2025 11:34:46
%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. - _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, <a href="/A002449/b002449.txt">Table of n, a(n) for n = 0..50</a>
%H A002449 A. Cayley, <a href="https://www.math.ucla.edu/~pak/papers/Cayley-comp.pdf">On a problem in the partition of numbers</a>, Philosophical Magazine (4) 13 (1857), 245-248; reprinted in his Collected Math. Papers, Vol. 3, pp. 247-249.
%H A002449 M. Cook and M. Kleber, <a href="https://doi.org/10.37236/1522">Tournament sequences and Meeussen sequences</a>, Electronic J. Comb. 7 (2000), #R44.
%H A002449 Olivier Danvy, <a href="https://arxiv.org/abs/2412.03127">Summa Summarum: Moessner's Theorem without Dynamic Programming</a>, arXiv:2412.03127 [cs.DM], 2024. See pp. 31, 33, 34.
%H A002449 Chams Lahlou, <a href="/A002449/a002449.pdf">A formula for some integer sequences that can be described by generating trees</a>
%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. (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,changed
%O A002449 0,3
%A A002449 _N. J. A. Sloane_
%E A002449 Recurrence and more terms from _Michael Kleber_, Dec 05 2000