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,3

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).

Formula

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

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 *)

Prog

(Magma) [2^Floor(n/2) + Floor((-1)^n - 1)/2: n in [0..50]]; // Vincenzo Librandi, Aug 17 2011
(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

Crossrefs

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

Sequence in context: A182712 A100818 A005291 * A028297 A207537 A114438

Adjacent sequences: A106621 A106622 A106623 * A106625 A106626 A106627

Keyword

easy,nonn

Author

Robert H Barbour, May 10 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

Status

approved