login
Maximum length of a codeword in Huffman encoding of n symbols, where the k-th symbol has frequency k.
3

%I #22 Nov 14 2024 17:10:55

%S 1,2,3,3,4,4,5,5,5,5,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9,

%T 9,9,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,

%U 10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11

%N Maximum length of a codeword in Huffman encoding of n symbols, where the k-th symbol has frequency k.

%H Cristina Ballantine, George Beck, Mircea Merca, and Bruce Sagan, <a href="https://arxiv.org/abs/2409.11268">Elementary symmetric partitions</a>, arXiv:2409.11268 [math.CO], 2024. See p. 20.

%H M. J. Fisher et al., <a href="https://drive.google.com/file/d/1VOM9IqzgOM1xZeq_KpDcpYRsvDLAa8iV/view">The birank number of a graph</a>, Congressus Numerant., 204 (2010), 173-180.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Huffman_coding">Huffman coding</a>

%F Conjecture: a(n) = floor(log_2(n)) + floor(log_2(2n/3)). Equivalently, a(n) = a(n-1) + 1 if n has the form 2^k or 3*2^k, 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 longest codewords have length a(8)=5.

%Y Cf. A126014 and A126237. The minimum length of a codeword is in A126235.

%K nonn

%O 2,2

%A _Dean Hickerson_, Dec 21 2006