Lehmer code
Encyclopedia
In mathematics
and in particular in combinatorics
, the terms inversion table and Lehmer code refer to ways to encode any permutation
of n by a sequence of n numbers in manner that makes evident the fact that there are
such permutations. 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 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 , 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 lexicographic 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 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 combinatorial number system representation of its position in the list of permutations of n in lexicographic 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.
The Lehmer code is named in reference to Derrick Henry Lehmer
, but the code had been known since 1888 at least .
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 {0, 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). 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 the boldface entry is subtracted from the larger entries to its right of it 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 {0, 1, … } as sequence numbers (which amounts to adding 1 to each entry if a permutation of {1, 2, … n} 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 {A,B,C,D,E,F,G} (which is B) then element 4 from {A,C,D,E,F,G} (which is F), then element 0 from {A,C,D,E,G} (giving A) and so on, reconstructing the sequence B,F,A,G,D,E,C.
Under the uniform law on the symmetric group
, the sequence L(σ) consists of independent and uniform variables; L(σ) follows the uniform law on }.
In other words, if we draw a permutation ω at random in
with equiprobability (each permutation has a probability of 1/n! to be chosen), then its Lehmer code ƒ=L(σ) is a sequence of random and uniform variables. The independence of the components of L results from a general principle concerning uniform variables on a Cartesian product
.
Let B(k) (resp. H(k)) be the event "there is right-to-left minimum (resp. maximum) at rank k" , i.e. B(k) is the set of the permutations
which exhibit a right-to-left minimum (resp. maximum) at rank k. We clearly have
Thus the number Nb(ω) (resp. Nh(ω)) of right-to-left minimum (resp. 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
The generating function
for the Bernoulli random variable
is
therefore the generating function of Nb is
which allow us to find again the product form for the generative series of the Stirling numbers of the first kind (unsigned).
The secretary problem
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).
In less mathematical words : a series of n applicants are interviewed one after the other. The interviewer must hire the best applicant, but must make his decision (“Hire” or “Not hire”) on the spot, without interviewing the next applicant ( and a fortiori without interviewing all applicants).
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.
To determine the optimal strategies (i.e. the strategy maximizing the probability of a win), the statistical properties of the Lehmer code are crucial.
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 elven prospective brides as his second wife. His first marriage had been an unhappy one, having been arranged without himself being consulted, and he was thus very concerned that he could reach the right decision.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and in particular in combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, the terms inversion table and Lehmer code refer to ways to encode any permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
of n by a sequence of n numbers in manner that makes evident the fact that there are
such permutations. 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 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 , 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 lexicographic 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 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 combinatorial number system representation of its position in the list of permutations of n in lexicographic 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.
The Lehmer code is named in reference to Derrick Henry Lehmer
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer was an American mathematician who refined Édouard Lucas' work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes...
, but the code had been known since 1888 at least .
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 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 {0, 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). 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 the boldface entry is subtracted from the larger entries to its right of it 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 {0, 1, … } as sequence numbers (which amounts to adding 1 to each entry if a permutation of {1, 2, … n} 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 {A,B,C,D,E,F,G} (which is B) then element 4 from {A,C,D,E,F,G} (which is F), then element 0 from {A,C,D,E,G} (giving A) and so on, reconstructing the sequence B,F,A,G,D,E,C.
Independence of relative ranks
This application stem from an immediate property of the Lehmer code L(σ) seen as a sequence of integers.Under the uniform law on the symmetric group
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
, the sequence L(σ) consists of independent and uniform variables; L(σ) follows the uniform law on }.In other words, if we draw a permutation ω at random in
with equiprobability (each permutation has a probability of 1/n! to be chosen), then its Lehmer code ƒ=L(σ) is a sequence of random and uniform variables. The independence of the components of L results from a general principle concerning uniform variables on a Cartesian productCartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
.
Number of right-to-left minima and maxima
Definition : In a sequence u(uk)1≤k≤n, there is right-to-left minimum (resp. maximum) at rank k if uk is strictly smaller (resp. strictly bigger) than each element ui with i>k, i.e., to its right.Let B(k) (resp. H(k)) be the event "there is right-to-left minimum (resp. maximum) at rank k" , i.e. B(k) is the set of the permutations
which exhibit a right-to-left minimum (resp. maximum) at rank k. We clearly haveThus the number Nb(ω) (resp. Nh(ω)) of right-to-left minimum (resp. 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
The generating function
Generating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
for the Bernoulli random variable
istherefore the generating function of Nb is
which allow us to find again the product form for the generative series of the Stirling numbers of the first kind (unsigned).
The secretary problemSecretary problemThe secretary problem is one of many names for a famous problem of theoptimal stopping theory.The problem has been studied extensively in the fields ofapplied probability, statistics, and decision theory...
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).In less mathematical words : a series of n applicants are interviewed one after the other. The interviewer must hire the best applicant, but must make his decision (“Hire” or “Not hire”) on the spot, without interviewing the next applicant ( and a fortiori without interviewing all applicants).
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.
To determine the optimal strategies (i.e. the strategy maximizing the probability of a win), the statistical properties of the Lehmer code are crucial.
Allegedly, Johannes Kepler
Johannes Kepler
Johannes Kepler was a German mathematician, astronomer and astrologer. A key figure in the 17th century scientific revolution, he is best known for his eponymous laws of planetary motion, codified by later astronomers, based on his works Astronomia nova, Harmonices Mundi, and Epitome of Copernican...
clearly exposed this secretary problem
Secretary problem
The secretary problem is one of many names for a famous problem of theoptimal stopping theory.The problem has been studied extensively in the fields ofapplied probability, statistics, and decision theory...
to a friend of his at a time when he was trying to make up his mind and choose one out elven prospective brides as his second wife. His first marriage had been an unhappy one, having been arranged without himself being consulted, and he was thus very concerned that he could reach the right decision.
See also
- PermutationPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
- Stirling numberStirling numberIn mathematics, Stirling numbers arise in a variety of combinatorics problems. They are named after James Stirling, who introduced them in the 18th century. Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second...
- Bernoulli distribution
- The secretary problemSecretary problemThe secretary problem is one of many names for a famous problem of theoptimal stopping theory.The problem has been studied extensively in the fields ofapplied probability, statistics, and decision theory...
- FactoradicFactoradicIn 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 digits...