The symmetric group
(SG
)
of degree n is the group of the
permutations (ListPerm
)
of the set . It is defined for any
n>0 and given a m>n, we have since we can
identify with the subgroup of by adding to any
permutation the fixed points . Using this embedding,
we define the group of all permutations of the set of positive
integers that fix all but a finite number of them:
We usually denote a permutation by the list of the images of under w, seen as a mapping of onto itself: .
A basic statistic on
permutations is the notion of inversion: given a permutation ,
an inversion is defined to be a couple of indices
such that and . We will refer to an inversion
on consecutive positions i and i+1 as a descent
(Perm2Desc
)
of the permutation and
conversely, we will talk about a rise of a given permutation w as a
position i such that .
The length
(Perm2Length
)
of a given permutation w is the number of
inversions of w, i.e. the cardinal of the set
(Inversions
)
of inversions of w:
The element of is called the maximal
permutation
(LastPerm
)
of because
it has the maximal number of inversions for the symmetric group of
degree n, i.e. the binomial .
The notion of inversion leads to another coding of the
elements of the symmetric group.
Given a permutation , we define the code
(Perm2Code
)
to be a vector of
non-negative integers, the i-th component being the number of positions j>i
such that .
One can
check that the length of the permutation w is the sum of all
components of the code . The code of the permutation
is .
Given a permutation , we can fill a square matrix with 0's and 1's so that the sub-matrix of 1's exactly represents the permutation w: this is done by having a 1 in all positions for where r denotes a row index and stands for a column index. All other values being set to 0. For instance, we show the square matrix representing the permutation ,
In a quite similar manner, we introduce the diagram of a permutation . This combinatorial object is defined to be a square matrix filled as follows: we put a circle at position (r, c) where r (respectively c) is a row index (resp. column index) whenever there is an inversion in which denotes the inverse permutation of w. Consider the element of , say , its diagram is the following:
since there is an inversion between the first position () and the value 1, between the second position () and the values 1,3,4 and 5 (second row of the previous diagram), and so on. The code of a permutation w can also be defined as the sequence of numbers of circles in the successive rows of the diagram .
Let be the elementary transposition that interchanges i and i+1, and fixes all other values. In other words, where i+1 lies at position i, or equivalently in which the unique 1 lies at position i. Elementary transpositions satisfy the following relations:
known as braid relations, together with the extra relation:
this last relation being changed into more general quadratic relations
to get the different Hecke algebras (NCA, IDCA, HEKA, HEQA
).
We constantly use the decomposition of a permutation as a product of simple
transpositions, product of minimal length, reduced decomposition
(Perm2Rd
).
This decomposition is far from being unique
(ListRd
): the number of reduced
decompositions is given by the function NbRd
.
Let us fix the convention used to multiply a permutation w by an elementary transposition :
where lies at position i, and
One can easily compute a reduced decomposition of a permutation w from its diagram. Reading the diagram from left to right and top to bottom, we replace each circle by a positive integer i starting from the row number, and increasing the value of i by 1 at each step. It gives a canonical reduced decomposition of the corresponding permutation by reading this Rothe diagram from right to left and downwards, each i being interpreted as the elementary transposition exchanging i and i+1. Given a permutation , its Rothe diagram is
from which we deduce a reduced decomposition of w, that is .
The set of reduced decompositions ranked according to their lengths, with
edges corresponding to simple transpositions, is called the
permutohedron, the order being the weak order: this is
the natural order for divided differences
(NCA
).
To the permutohedron, one can add edges between permutations which differ
by a transposition and with lengths differing by 1. The order is now called
the Bruhat order, and is the natural order for the idCoxeter algebra
(IDCA
).
The interval of permutations below a given one is obtained with the function
Interval
;
Betti
(perm) gives the number
of permutations in the interval corresponding to the permutation perm according
to their lengths.