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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

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^3-1/2*x^2+1/2)/(x^4-3/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

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 November 21 16:08 EST 2017. Contains 295003 sequences.