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