%I #37 Sep 27 2022 08:44:29
%S 1,0,2,1,4,3,8,7,16,15,32,31,64,63,128,127,256,255,512,511,1024,1023,
%T 2048,2047,4096,4095,8192,8191,16384,16383,32768,32767,65536,65535,
%U 131072,131071,262144,262143,524288,524287,1048576,1048575,2097152
%N Expansion of g.f.: (1 - x^2 + x^3)/((1-x^2)*(1-2*x^2)).
%C 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.
%D Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), (1979), Volume 11 Issue 2.
%D Huffman, D. A., A method for the construction of minimum redundancy codes, Proc. IRE 40 (1951), 1098-1101.
%D Knuth, D. E., Dynamic Huffman coding. J. Algorithms 6 (1985), 163-180.
%H Vincenzo Librandi, <a href="/A106624/b106624.txt">Table of n, a(n) for n = 0..5000</a>
%H G. C. Barnes et al., <a href="https://doi.org/10.1145/1047124.1047408">Balanced sample Binary Trees</a>, ACM SIGCSE Bulletin, Volume 37 Issue 1, 2005 pp. 166-170.
%H P. N. Fenwick, <a href="https://web.archive.org/web/20030522104516/http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf">Cumulative Frequency</a>, Software: Practice and Experience, 1994.
%H C. Witteveen, <a href="https://web.archive.org/web/20091122101853/http://pds.twi.tudelft.nl/vakken/in444/in4026-2.pdf">Balanced Binary Trees</a>, Slides.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,3,0,-2).
%F a(n) = 2^floor(n/2) + floor((-1)^n - 1)/2. - _N. J. A. Sloane_, May 15 2005
%p A106624 := proc(N)
%p 2^floor(n/2)+((-1)^n-1)/2 ;
%p end proc:
%p seq(A106624(n),n=0..20) ; # _R. J. Mathar_, Apr 14 2018
%t Table[2^Floor[n/2] +Floor[(-1)^n-1]/2, {n,0,50}] (* _G. C. Greubel_, Feb 19 2019 *)
%o (Magma) [2^Floor(n/2) + Floor((-1)^n - 1)/2: n in [0..50]]; // _Vincenzo Librandi_, Aug 17 2011
%o (PARI) vector(50,n, n--; 2^floor(n/2) +floor((-1)^n-1)/2) \\ _G. C. Greubel_, Feb 19 2019
%o (Sage) [2^floor(n/2) +floor((-1)^n-1)/2 for n in (0..50)] # _G. C. Greubel_, Feb 19 2019
%Y Cf. A016116, A014535, A037026, A058518 - A058521, A000079 (bisection), A000225 (bisection).
%K easy,nonn
%O 0,3
%A _Robert H Barbour_, May 10 2005
%E New definition from _N. J. A. Sloane_, May 15 2008
%E Edited by _N. J. A. Sloane_, Aug 29 2008 at the suggestion of _R. J. Mathar_