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

Rothe diagram and inversions