For anybody who is interested, here are two online video lecture series from Stanford University:
Statistical Aspects of Data Mining
Also, the data set for the netflix prize.
Despite numerous other unfinished projects, I have decided to learn Ruby.
Regardless of whether you have any actual interest in learning Ruby or not, if your laughing muscles need a work out, may I recommend:
Why’s (poignant) guide to Ruby
It even has a soundtrack.
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 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:
Here’s just a quick post of a plot I did a quite a while back:
This animation shows for 
through to 
the number of permutations with a given number of inversions and major index. I love the way that discrete structure slowly falls away into something nearly continuous. I would have included more frames in the animation, but as there are 
permutations in 
it gets expensive to compute these by brute force counting. I would need to come up with a more effective method.
An inversion of a permutation on 
is a pair of elements with 
such that 
That is, the permutation reverses their order. The inversion number, 
is the number of such pairs that a given permutation has. For example, the permutation 
(regarded as a word, not a cycle) has inversions 
and so 
A descent in a permutation is a position with 
where a larger number occurs immediately before a smaller one. That is, 
The major index, 
is defined as the sum of the descents. For example, in the permutation we have descents at the first position (3 falls to 1), and at the third (4 falls to 2). So the major index of this permutation is 
The plot shows at position the number of permutations with exactly inversions, and major index 
as a normalised shade of grey, darker meaning larger. Indices increase left to right and top to bottom.
You can easily see from the symmetry of the plots that permutations are equidistributed with respect to these two indices, so that we can expect the polynomial where the coefficient of 
is the number of permutations with inversion number and major index will be a symmetric polynomial in 
and 
Also, the sage-combinat-dev mailing list.
So, why am I still fumbling along trying to implement inefficient algorithms for basic algebraic and combinatorial structures in Haskell, when efficient versions already exist in this fabulous open source project? Well:
The Anatomy of Integers and Permutations.
The best part is – they even made it into a screen play.