Run-length encoding

This article needs more work.

Please help by expanding it!

Run-length encoding (or runlength encoding) means converting a list of values to as a list of pairs consisting of each single value together with its count (the length of its "run").

Binary run-length encoding

When there are at maximum two distinct values present, say 0 and 1, then only the run-lengths are needed to recover the original list of values, as it is always known of what value the next run consists of. By representing natural numbers in binary numeral system and starting from the left, i.e. the most significant bit, which is always 1 for $\scriptstyle n\geq 1\,$, each natural number is converted unambiguously to a finite tuple of natural numbers:

1 $\rightarrow$ binary 1 $\rightarrow$ tuple: (1)

2 $\rightarrow$ binary 10 $\rightarrow$ tuple: (1 1)

3 $\rightarrow$ binary 11 $\rightarrow$ tuple: (2)

4 $\rightarrow$ binary 100 $\rightarrow$ tuple: (1 2)

5 $\rightarrow$ binary 101 $\rightarrow$ tuple: (1 1 1)

6 $\rightarrow$ binary 110 $\rightarrow$ tuple: (2 1)

7 $\rightarrow$ binary 111 $\rightarrow$ tuple: (3)

Furthermore, one can adopt the convention that zero (binary 0) corresponds to the empty tuple ( ). (The empty tuple ( ) gives the empty sum, i.e. 0, since every digit corresponds to a summand.)

Applications for further encoding techniques

Coding integer compositions

Each finite tuple of natural numbers gives an integer composition of the number to which its elements sum to. Because this number, via the mapping presented above, is equal to the binary length of the integer which encodes the tuple, the nonnegative integers (A001477) encode the integer compositions in their size-wise order. (See Binary representation ordering of the integer compositions.)

Coding integer partitions

By interpreting the first element of the tuple as the first element of the partition, and the rest (after one is subtracted from each) as successive differences between parts, also integer partitions can be encoded. See A129594 and .

Coding balanced parenthesizations

If one is subtracted from each $\scriptstyle n_{i}\,$ in the tuple $\scriptstyle (n_{1},\,n_{2},\,\ldots ,\,n_{k})\,$ and then the same $\scriptstyle n\,{\rightarrow }\,{\rm {tuple}}\,$ conversion, together with subtraction by one, is done recursively, as far down to each branch until zeros are encountered, which are then converted to empty tuples ( ), one obtains balanced parenthesizations, one of the combinatorial interpretations of Catalan numbers. (See Binary runlength encoding of general trees/parenthesizations.)