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 :

**. Lemma **
*For each and each we have
*

*
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 .
*

**Exercises**

Sun Feb 05 18:28:26 MET 1995