In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encode each possible permutation of a sequence of n numbers.
[2] The Lehmer code makes use of the fact that there are permutations of a sequence of n numbers.
While several encodings 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 n − i, allowing for n + 1 − i different values.
Other properties of the Lehmer code include that the lexicographical order 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 σi smaller than any σj to its right), and a value n − i at position i similarly signifies a right-to-left maximum, and that the Lehmer code of σ coincides with the factorial number system 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 σj 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.
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.
Another method which is in-place, but not really more efficient, is to start with the permutation of {0, 1, ... n − 1} 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).
The Lehmer code defines a bijection from the symmetric group Sn to the Cartesian product
As a consequence, under the uniform distribution on Sn, the component L(σ)i defines a uniformly distributed random variable on [n − i], and these random variables are mutually independent, because they are projections on different factors of a Cartesian product.
maximum) for the permutation ω can be written as a sum of independent Bernoulli random variables each with a respective parameter of 1/k : Indeed, as L(k) follows the uniform law on
This is an optimal stop problem, a classic in decision theory, statistics and applied probabilities, where a random permutation is gradually revealed through the first elements of its Lehmer code, and where the goal is to stop exactly at the element k such as σ(k)=n, whereas the only available information (the k first values of the Lehmer code) is not sufficient to compute σ(k).
The interviewer thus knows the rank of the kth applicant, therefore, at the moment of making his kth decision, the interviewer knows only the k first elements of the Lehmer code whereas he would need to know all of them to make a well informed decision.
Allegedly, Johannes Kepler clearly exposed this secretary problem to a friend of his at a time when he was trying to make up his mind and choose one out eleven prospective brides as his second wife.