TAOCP and the inversion table of a permutation.

Perhaps every body in Computer science knows Knuth's volumes of "the art of computer programming".
Since I was not a in a cs undergraduate program, I knew this book even before
any introductory algorithm book like "Introduction to Algorithms".
Partly due to the comment made by Bill Gate on the back of the 1st volumes: "If you think you're a really good programmer . . . read (Knuth's) Art of Computer Programming . . . You should definitely send me a resume if you can read the whole thing.", I started reading the book, as my very first book on algorithms (I had read some books about c and vb programming before, but I wouldn't count them as algorithm books).
It was like 5 years back, I could only read 2-3 pages per day. Eventually I finished two volumes (the 1st and 3rd vol). I still remember many exciting moments when I managed to understand the contents, full of numerous amazing algorithms and beautiful analysis. The book does not only convey the knowledge of which the big vols already contain a incredibly amount,
but also an aesthetic point of view towards algorithms by providing a large number of masterpieces that best illustrate it. I probably should say, the topics discussed in the book is arguably bit old-fashined and these volumes do not appear in papers' ref as frequently in nowadays cs research as 3o years ago. However, many tricks covered in the book can still be very useful.

Today, I will discuss a very cute one, the inversion table for a permutation. The definition is very simple.
Given a permutation P of {1,2,....,n}, its inversion table is a length n sequence
b1,b2,...,bn where bi= #(elements that are bigger than i and appear to the left of i in P.

e.g. P= {591826473}
its inverse table is {236402210}. b1=2 since there are two elements (5 and 9) larger than and on the LHS of 1.

A easy observation is an inversion table uniquely determines a permutation.
It is at times much more convenient to work with inversion tables than original permutations since the space of inversion tables looks much simpler:
actually, every sequence b1b2....bn with 0<=bi<=n-i corresponds to some inversion table!
(Note we also have n*(n-1)*....*1=n! many of them.)

Let us see an application.
Compute the expected number of right-to-left maxima for a random permutation of {1,2,...,n}.
This was one problem in the final exam of our probabilistic method course taught by Aravind Srinivasan.
Direct computation would be rather cumbersome. I remember I spent like 20min on manipulating binomial coefficients and got nowhere...
Let us work with the inversion table b1b2...bn now.
We can see the number i is a right-to-left maxima if and only if bi=n-i (all n-i larger numbers are all to its left).
Also taking a random permutation is equivalent to taking a random inversion table since the 1-1 correspondence.
Therefore,
E= \sum_{i=1}^n Pr(i is a right-left maximum)=\sum_{i=1}^n Pr(bi=n-i)= \sum_{i=1}^n 1/(n-i+1) = H_n (the n-th harmonic number).

Cute, isn't it!


Another solution I know is to use the following recurrence:

E[#maxima w.r.t {1...n}] = \sum_{i=1}^n Prob(first element is i) (E[#maxima w.r.t {i+1...n}]+1)
which reduces to the recursion
E(n)= \sum_{i=0}^{n-1}(E(n-i)+1)/n.
The nth harmonich number H_n solves this recursion.
This is as simple, but way less cute, I think.