A126014 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

A126014

Triangle read by rows, based on Huffman encoding. See comments.

2, 3, 2, 2, 3, 2, 5, 2, 6, 3, 2, 8, 3, 2, 9, 5, 2, 5, 2, 6, 3, 2, 8, 3, 2, 9, 5, 2, 11, 5, 2, 12, 6, 3, 2, 14, 6, 3, 2, 15, 8, 3, 2, 17, 8, 3, 2, 18, 9, 5, 2, 20, 9, 5, 2, 21, 11, 5, 2, 11, 5, 2, 12, 6, 3, 2, 14, 6, 3, 2, 15, 8, 3, 2, 17, 8, 3, 2, 18, 9, 5, 2, 20, 9, 5, 2, 21, 11, 5, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

Row #n pertains to Huffman encoding of n symbols, where the k-th symbol has frequency k. Let b(k) be the number of bits used to encode the symbol of frequency k. The row has the values of k such that b(k)>b(k+1).

Each row is ordered descendingly; each ends with '2'. Row #3 is first.

LINKS

Table of n, a(n) for n=1..90.

Wikipedia, Huffman coding

EXAMPLE

In row #8, the frequencies are 1,2,3,4,5,6,7,8 and a Huffman encoding is (1->00000, 2->00001, 3->0001, 4->001, 5->010, 6->011, 7->10, 8->11). The codes shrink after k=6,3,2; so row #8 has 6,3,2.

2; 3,2; 2; 3,2; 5,2; 6,3,2; 8,3,2; 9,5,2; 5,2; 6,3,2; 8,3,2; ...

CROSSREFS

The length of the n-th row is in A126237. The minimum and maximum lengths of codewords are in A126235 and A126236.

Sequence in context: A372971 A241604 A282900 * A317420 A256795 A273404

Adjacent sequences: A126011 A126012 A126013 * A126015 A126016 A126017

KEYWORD

nonn,tabf

AUTHOR

Serhat Sevki Dincer (mesti_mudam(AT)yahoo.com), Dec 14 2006

EXTENSIONS

Edited by Don Reble, Dec 17 2006 and Dean Hickerson, Dec 21 2006

STATUS

approved