This site is supported by donations to The OEIS Foundation.

Run-length encoding

From OeisWiki
Jump to: navigation, search

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").[1]

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 , each natural number is converted unambiguously to a finite tuple of natural numbers:

1 binary 1 tuple: (1)
2 binary 10 tuple: (1 1)
3 binary 11 tuple: (2)
4 binary 100 tuple: (1 2)
5 binary 101 tuple: (1 1 1)
6 binary 110 tuple: (2 1)
7 binary 111 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 [2].

Coding balanced parenthesizations

If one is subtracted from each in the tuple and then the same 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.)


  1. Run-length encoding —
  2. Marc LeBrun's original "crazy order" mapping for partitions (Note that the encoding represented here uses the exponent tuple of prime factorization instead of run lengths of binary expansion.)