A106624 Expansion of g.f.: (1 - x^2 + x^3)/((1-x^2)*(1-2*x^2)).

1, 0, 2, 1, 4, 3, 8, 7, 16, 15, 32, 31, 64, 63, 128, 127, 256, 255, 512, 511, 1024, 1023, 2048, 2047, 4096, 4095, 8192, 8191, 16384, 16383, 32768, 32767, 65536, 65535, 131072, 131071, 262144, 262143, 524288, 524287, 1048576, 1048575, 2097152

Offset: 0

Author

Robert H Barbour, May 10 2005

Keywords

• easy
• nonn

Comments

Cumulative column frequency of occurrence of 0's and 1's iterated in a binary tree where each node in the tree holds a value of 0 or 1, beginning with a count of 1.

References

• Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), (1979), Volume 11 Issue 2.
• Huffman, D. A., A method for the construction of minimum redundancy codes, Proc. IRE 40 (1951), 1098-1101.
• Knuth, D. E., Dynamic Huffman coding. J. Algorithms 6 (1985), 163-180.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..5000
• G. C. Barnes et al., Balanced sample Binary Trees, ACM SIGCSE Bulletin, Volume 37 Issue 1, 2005 pp. 166-170.
• P. N. Fenwick, Cumulative Frequency, Software: Practice and Experience, 1994.
• C. Witteveen, Balanced Binary Trees, Slides.
• Index entries for linear recurrences with constant coefficients, signature (0,3,0,-2).

Crossrefs

Cf. A016116, A014535, A037026, A058518 - A058521, A000079 (bisection), A000225 (bisection).

Programs

Magma

[2^Floor(n/2) + Floor((-1)^n - 1)/2: n in [0..50]]; // Vincenzo Librandi, Aug 17 2011

Maple

A106624 := proc(N)
    2^floor(n/2)+((-1)^n-1)/2 ;
end proc:
seq(A106624(n),n=0..20) ; # R. J. Mathar, Apr 14 2018

Mathematica

Table[2^Floor[n/2] +Floor[(-1)^n-1]/2, {n,0,50}] (* G. C. Greubel, Feb 19 2019 *)

PARI

vector(50,n, n--; 2^floor(n/2) +floor((-1)^n-1)/2) \\ G. C. Greubel, Feb 19 2019

Sage

[2^floor(n/2) +floor((-1)^n-1)/2 for n in (0..50)] # G. C. Greubel, Feb 19 2019

Formula

a(n) = 2^floor(n/2) + floor((-1)^n - 1)/2. - N. J. A. Sloane, May 15 2005

Extensions

New definition from N. J. A. Sloane, May 15 2008

Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar