The Lehmer code is the sequence of numbers of white buttons in the columns of
If it is clear which is meant, then we may replace by the shorter sequence
arising from by canceling the zeros at the end of , for example
It is not difficult to see how can be reconstructed from . Clearly is the -th element of , with respect to the natural order of . Correspondingly, is the -th element of , and so on. For example
Furthermore, each , , is , i.e.
Since there are such sequences in , we have obtained:
. Corollary The Lehmer code establishes a bijection between and the set of sequences in , , for each .
This shows that in fact the Lehmer code is a code for permutations.
But there is much more to say about Lehmer codes. Applying the equivalences
we can easily derive (exercise ) that right multiplication of by the elementary transposition has the following effect on :
For each and each we have
if , while
if , while
The main point is that the shift from to amounts (cf. ) to an increase or a decrease in
by 1. Hence the following holds:
. Corollary The sum of the entries of the Lehmer code of is equal to the minimal number of elementary transpositions which are needed in order to express as a product of elementary transpositions. Moreover, this yields a canonic way of expressing as a product of elementary transpositions by decreasing the rightmost nonzero entry of the Lehmer code by 1 and iterating this process until each entry is equal to zero.
We therefore call the reduced length of and we call such an expression of as a product of elementary transpositions, which is of minimal length, a reduced decomposition. A reduced decomposition of for example, is obtained from the following sequence of manipulations of Lehmer codes, according to :
This shows that
is a reduced decomposition. Try to compute the reduced composition of some permutations.
The lemma also shows how we can obtain all the reduced decompositions of a given permutation:
. Corollary The complete set of reduced decompositions of is obtained by carrying out all the successive multiplications that reduce the Lehmer sequence by 1, according to .
E . Check .