The Lehmer code
is the sequence of numbers of white buttons in the columns of 
For example
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 :
if
.
Lemma
For each and each 
we have
, 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 .
Exercises
.