In
mathematics and in particular in
combinatorics, the Lehmer code is a particular way to
encode
The Encyclopedia of DNA Elements (ENCODE) is a public research project which aims to identify functional elements in the human genome.
ENCODE also supports further biomedical research by "generating community resources of genomics data, software ...
each possible
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pr ...
of a sequence of ''n'' numbers. It is an instance of a scheme for
numbering permutations and is an example of an
inversion
Inversion or inversions may refer to:
Arts
* , a French gay magazine (1924/1925)
* ''Inversion'' (artwork), a 2005 temporary sculpture in Houston, Texas
* Inversion (music), a term with various meanings in music theory and musical set theory
* ...
table.
The Lehmer code is named in reference to
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s an ...
, but the code had been known since 1888 at least.
The code
The Lehmer code makes use of the fact that there are
:
permutations of a sequence of ''n'' numbers. If a permutation ''σ'' is specified by the sequence (''σ''
1, …, ''σ''
''n'') of its images of 1, …, ''n'', then it is encoded by a sequence of ''n'' numbers, but not all such sequences are valid since every number must be used only once. By contrast the encodings considered here choose the first number from a set of ''n'' values, the next number from a fixed set of values, and so forth decreasing the number of possibilities until the last number for which only a single fixed value is allowed; ''every'' sequence of numbers chosen from these sets encodes a single permutation. While several
encoding
In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication ...
s can be defined, the Lehmer code has several additional useful properties; it is the sequence
:
in other words the term ''L''(''σ'')
''i'' counts the number of terms in (''σ''
1, …, ''σ''
''n'') to the right of ''σ''
''i'' that are smaller than it, a number between 0 and , allowing for different values.
A pair of indices (''i'',''j'') with and is called an inversion of ''σ'', and ''L''(''σ'')
''i'' counts the number of inversions (''i'',''j'') with ''i'' fixed and varying ''j''. It follows that is the total number of inversions of ''σ'', which is also the number of adjacent transpositions that are needed to transform the permutation into the identity permutation. Other properties of the Lehmer code include that the
lexicographical order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
of the encodings of two permutations is the same as that of their sequences (''σ''
1, …, ''σ''
''n''), that any value 0 in the code represents a right-to-left minimum in the permutation (i.e., a smaller than any to its right), and a value
at position ''i'' similarly signifies a right-to-left maximum, and that the Lehmer code of ''σ'' coincides with the
factorial number system
In combinatorics, the factorial number system, also called factoradic, is a mixed radix numeral system adapted to numbering permutations. It is also called factorial base, although factorials do not function as base, but as place value of digi ...
representation of its position in the list of permutations of ''n'' in lexicographical order (numbering the positions starting from 0).
Variations of this encoding can be obtained by counting inversions (''i'',''j'') for fixed ''j'' rather than fixed ''i'', by counting inversions with a fixed smaller ''value'' rather than smaller index ''i'', or by counting non-inversions rather than inversions; while this does not produce a fundamentally different type of encoding, some properties of the encoding will change correspondingly. In particular counting inversions with a fixed smaller value gives the inversion table of ''σ'', which can be seen to be the Lehmer code of the inverse permutation.
Encoding and decoding
The usual way to prove that there are ''n''! different permutations of ''n'' objects is to observe that the first object can be chosen in different ways, the next object in different ways (because choosing the same number as the first is forbidden), the next in different ways (because there are now 2 forbidden values), and so forth. Translating this freedom of choice at each step into a number, one obtains an encoding algorithm, one that finds the Lehmer code of a given permutation. One need not suppose the objects permuted to be numbers, but one needs a
total ordering
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
of the set of objects. Since the code numbers are to start from 0, the appropriate number to encode each object ''σ''
''i'' by is the number of objects that were available at that point (so they do not occur before position ''i''), but which are smaller than the object ''σ''
''i'' actually chosen. (Inevitably such objects must appear at some position , and (''i'',''j'') will be an inversion, which shows that this number is indeed ''L''(''σ'')
''i''.)
This number to encode each object can be found by direct counting, in several ways (directly counting inversions, or correcting the total number of objects smaller than a given one, which is its sequence number starting from 0 in the set, by those that are unavailable at its position). Another method which is in-place, but not really more efficient, is to start with the permutation of obtained by representing each object by its mentioned sequence number, and then for each entry ''x'', in order from left to right, correct the items to its right by subtracting 1 from all entries (still) greater than ''x'' (to reflect the fact that the object corresponding to ''x'' is no longer available). Concretely a Lehmer code for the permutation B,F,A,G,D,E,C of letters, ordered alphabetically, would first give the list of sequence numbers 1,5,0,6,3,4,2, which is successively transformed
:
where the final line is the Lehmer code (at each line one subtracts 1 from the larger entries to the right of the boldface element to form the next line).
For decoding a Lehmer code into a permutation of a given set, the latter procedure may be reversed: for each entry ''x'', in order from right to left, correct the items to its right by adding 1 to all those (currently) greater than or equal to ''x''; finally interpret the resulting permutation of as sequence numbers (which amounts to adding 1 to each entry if a permutation of is sought). Alternatively the entries of the Lehmer code can be processed from left to right, and interpreted as a number determining the next choice of an element as indicated above; this requires maintaining a list of available elements, from which each chosen element is removed. In the example this would mean choosing element 1 from (which is B) then element 4 from (which is F), then element 0 from (giving A) and so on, reconstructing the sequence B,F,A,G,D,E,C.
Applications to combinatorics and probabilities
Independence of relative ranks
The Lehmer code defines a bijection from the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \ ...
''S''
''n'' to the Cartesian product