|
%I #12 Jun 27 2021 11:57:04
%S 1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,
%T 4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
%U 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6
%N Minimum length of a codeword in Huffman encoding of n symbols, where the k-th symbol has frequency k.
%D M. J. Fisher et al., The birank number of a graph, Congressus Numerant., 204 (2010), 173-180.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Huffman_coding">Huffman coding</a>
%F Conjecture: a(n) = A099396(n+1) = floor(log_2(2(n+1)/3)). Equivalently, a(n) = a(n-1) + 1 if n has the form 3*2^k-1, a(n) = a(n-1) otherwise. This is true at least for n up to 1000.
%e A Huffman code for n=8 is (1->00000, 2->00001, 3->0001, 4->001, 5->010, 6->011, 7->10, 8->11). The shortest codewords have length a(8)=2.
%Y Cf. A099396, A126014 and A126237. The maximum length of a codeword is in A126236.
%K nonn
%O 2,4
%A _Dean Hickerson_, Dec 21 2006
|
