Inversions in permutations and words
An inversion in a permutation 
is a pair 
of indices such that
but 
. Let 
denote the total number of inversions of 
. One can uniquely record a permutation by recording, for each 
the number of inversions , which will be a number from 
to 
. One can recover the 
entry of the permutation (and hence the whole permutation) from such a recording by the following algorithm. Let 
be the set of the first 
entries of the permutation. If the number of inversions of the form is 
, then there must be exactly elements after the position which are smaller than it. Hence, the entry of the permutation is the 
smallest element of 
.
Hence,
is a weight preserving bijection, where
is the usual additive weight.
By simply reversing the sequences (using the index substitution 
), we get a further bijection:
So these two sets will have the same generating series. Using the product and sum lemma, we obtain:
We now extend the definition of inversions to words on the alphabet 
. If 
is the symbol at the position of the word 
, then an inversion in is a pair of positions such that , but 
.
We wish to know the generating series with respect to inversions for the set 
of words of length 
on with 
occurrences of 
.
To get it, we will use an indirect decomposition, decomposing an element as a word 
, together with permutations 
in a bijection which additively preserves inversions, where 
and 
is a set with elements.
That is, our weight-preserving bijection will look like:
We split the domain of a permutation into blocks with sizes 
in the obvious way, with the block consisting of the elements 
where 
. Note that 
acts on in a canonical way, with a permutation 
sending 
to 
.
The word is then defined by 
if 
.
We define the permutation 
for each 
as the subword of consisting of the elements of . Note that if 
and 
are both elements of , then 
is an inversion of if and only if it is also is an inversion of .
It will help to illustrate this bijection with an example. Take 
, 
and 
, so that 
, 
and 
.
Let 
be the permutation (in word form):
Then we construct the word 
by taking to be the block in which 
occurs:
We then compute:
To invert the above process, we simply replace the 
occurrence of in the word with 
. Hence, this is a bijection.
To see that it is additively weight-preserving with respect to inversions, we do a bit of a case analysis. We classify the inversions of according to whether 
and 
are in the same block or in different blocks.
If they are in different blocks, say 
and 
, then since 
, we must have 
, and so 
. Hence is also an inversion of . Conversely, every inversion of will clearly be an inversion of of this type, since if 
but 
, we have that and , but since , any element of is greater than any element of 
, and in particular .
If they are in the same block , then by a previous argument, is an inversion of if and only if it is an inversion of .
Hence, we have that 
.
By subtracting 
from each of the elements of , we obtain a standard permutation 
, and this is obviously inversion-preserving.
So, we have a weight-preserving bijection:
Hence, we have a corresponding equation of generating series. Let 
be the generating series for
. Then:
and hence,
