login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002449 Number of different types of binary trees of height n.
(Formerly M1683 N0664)
14
1, 1, 2, 6, 26, 166, 1626, 25510, 664666, 29559718, 2290267226, 314039061414, 77160820913242, 34317392762489766, 27859502236825957466, 41575811106337540656038, 114746581654195790543205466 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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. [From 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

M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.

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)

EXAMPLE

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

MAPLE

d := proc(n) option remember; if n=0 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 *)

PROG

(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 */

CROSSREFS

Cf. A001699, A056207, A098539, A018819.

Sequence in context: A141713 A005272 A178089 * A059430 A288607 A086584

Adjacent sequences:  A002446 A002447 A002448 * A002450 A002451 A002452

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Recurrence and more terms from Michael Kleber, Dec 05 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 07:21 EDT 2018. Contains 316337 sequences. (Running on oeis4.)