

A106624


G.f.: (1  x^2 + x^3)/(1  3*x^2 + 2*x^4).


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 BTree, 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), 10981101.
Knuth, D. E., Dynamic Huffman coding. J. Algorithms 6 (1985), 163180.


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
Barnes, G.C. et al., Balanced sample Binary Trees .
Fenwick, P.N. Cumulative Frequency.
Witteveen, C.Balanced Binary Trees .
Index entries for linear recurrences with constant coefficients, signature (0,3,0,2).


FORMULA

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


MAPLE

A106624 := proc(n) coeftayl( (1/2*x^31/2*x^2+1/2)/(x^43/2*x^2+1/2), x=0, n) ; end: seq(A106624(n), n=0..80) ; # R. J. Mathar, Feb 13 2008


PROG

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


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
More terms from R. J. Mathar, Feb 13 2008
Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar


STATUS

approved



