A002449 Number of different types of binary trees of height n.
1, 1, 2, 6, 26, 166, 1626, 25510, 664666, 29559718, 2290267226, 314039061414, 77160820913242, 34317392762489766, 27859502236825957466, 41575811106337540656038, 114746581654195790543205466, 588765612737696531880325270438, 5642056933026209681424588087899226
Offset: 0
Examples
G.f. = 1 + x + 2*x^2 + 6*x^3 + 26*x^4 + 166*x^5 + 1626*x^6 + 25510*x^7 + ...
References
- 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.
- 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
- R. F. Churchhouse, Congruence properties of the binary partition function. Proc. Cambridge Philos. Soc. 66 1969 371-376.
- 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. E. Knuth, Selected Papers on Analysis of Algorithms, p. 75 (gives asymptotic formula and lower bound).
- H. Minc, The free commutative entropic logarithmetic. Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).
- 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.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- T. D. Noe, Table of n, a(n) for n = 0..50
- 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.
- M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.
- Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See pp. 31, 33, 34.
- Chams Lahlou, A formula for some integer sequences that can be described by generating trees
Programs
-
Maple
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
-
Mathematica
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 *) -
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
-
PARI
a(n)=polcoeff(1/prod(k=0,n,1-x^(2^k)+O(x^(2^n))),2^n-1)
-
PARI
{a(n, k=2) = if(n<2, n>=0, sum(i=1, k, a(n-1, 2*i)))}; /* Michael Somos, Nov 24 2016 */
Formula
a(n) = A098539(n, 1). - Paul D. Hanna, Sep 13 2004
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
From Benedict W. J. Irwin, Nov 16 2016: (Start)
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:
a(3) = Sum_{i=1..2} 2*i.
a(4) = Sum_{i=1..2}Sum_{j=1..2*i} 2*j.
a(5) = Sum_{i=1..2}Sum_{j=1..2*i}Sum_{k=1..2*j} 2*k. (End)
The conjecture is true: see Links. - Chams Lahlou, Jan 26 2019
Extensions
Recurrence and more terms from Michael Kleber, Dec 05 2000
Comments