| | | **Rothe diagram and inversions** |

### Rothe diagram and inversions

Another way of
describing permutations * pÎS*_{n} is the *list notation,*
where we put the list
of their values in square brackets:
* 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)* of * p* by a white button
* o * at *( pj,i),* then we fill exactly the boxes of the Rothe diagram
of * p* where 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@kfunigraz.ac.at,

last changed: August 28, 2001

| | | **Rothe diagram and inversions** |