Rothe diagram and inversions |

Another way of
describing permutations * pÎS _{n} * is the

p=[ p1, ..., pn], or p=[ p1 ...pn], if possible.

In order to visualize permutations we can use a board consisting of boxes in the
second quadrant, where we put a black button * ·* into the box with the pair of coordinates
*(i,k)* if and only *k= pi,*
obtaining the *Rothe diagram*
*R( p)* of * p.* This diagram was introduced by
H. A. Rothe already in 1800. For example
*R([54132])* is equal to
The list notation gives rise to the *Lehmer code*
which we are going to describe next. In order to do this we consider
the *set* *I( p)* of inversions of * p*:

I( p):= {(i,j) În^{2}| i<j, pi> pj }.

An easy check (exercise) shows that the following holds:

Lemma:If we represent the inversion(i,j)ofpby a white buttonoat( pj,i),then we fill exactly the boxes of the Rothe diagram ofpwhere the black button of the row is in a column to the right and where the black button of the column is lower down.

The resulting diagram * L( p)* is called the *Lehmer diagram*
of * p*. For example, the superposition of the Rothe diagram and the Lehmer
diagram of * p:=[54132]* is
There is a program, which calculates the
number of inversions
of a given permutation.

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Rothe diagram and inversions |