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
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).
Crossrefs
Programs
-
Magma
[2^Floor(n/2) + Floor((-1)^n - 1)/2: n in [0..50]]; // Vincenzo Librandi, Aug 17 2011
-
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 *) -
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
Formula
a(n) = 2^floor(n/2) + floor((-1)^n - 1)/2. - N. J. A. Sloane, May 15 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
Comments