A002449 - OEIS

%I M1683 N0664 #71 Dec 10 2024 12:29:40

%S 1,1,2,6,26,166,1626,25510,664666,29559718,2290267226,314039061414,

%T 77160820913242,34317392762489766,27859502236825957466,

%U 41575811106337540656038,114746581654195790543205466,588765612737696531880325270438,5642056933026209681424588087899226

%N Number of different types of binary trees of height n.

%C Two trees have the same type if they have the same number of nodes at each level. - _Chams Lahlou_, Jan 26 2019

%C 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 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 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 R. F. Churchhouse, Congruence properties of the binary partition function. Proc. Cambridge Philos. Soc. 66 1969 371-376.

%D 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 D. E. Knuth, Selected Papers on Analysis of Algorithms, p. 75 (gives asymptotic formula and lower bound).

%D H. Minc, The free commutative entropic logarithmetic. Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).

%D 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A002449/b002449.txt">Table of n, a(n) for n = 0..50</a>

%H 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 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 Chams Lahlou, <a href="/A002449/a002449.pdf">A formula for some integer sequences that can be described by generating trees</a>

%F a(n) = A098539(n, 1). - _Paul D. Hanna_, Sep 13 2004

%F 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 From  _Benedict W. J. Irwin_, Nov 16 2016: (Start)

%F 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 a(3) = Sum_{i=1..2} 2*i.

%F a(4) = Sum_{i=1..2}Sum_{j=1..2*i} 2*j.

%F a(5) = Sum_{i=1..2}Sum_{j=1..2*i}Sum_{k=1..2*j} 2*k.

%F (End)

%F The conjecture is true: see Links. - _Chams Lahlou_, Jan 26 2019

%e G.f. = 1 + x + 2*x^2 + 6*x^3 + 26*x^4 + 166*x^5 + 1626*x^6 + 25510*x^7 + ...

%p 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 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 (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 (PARI) a(n)=polcoeff(1/prod(k=0,n,1-x^(2^k)+O(x^(2^n))),2^n-1)

%o (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 Cf. A001699, A056207, A098539, A018819.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_

%E Recurrence and more terms from _Michael Kleber_, Dec 05 2000