# The generating function for permutations indexed by number of inversions

For $\sigma\in S_n$ an inversion is a pair $(\sigma_i,\sigma_j)$ such that $i<j$ and $\sigma_i>\sigma_j$.

Could you help me to prove that the generating function of $S_n$ by number of inversions is

$(1+x)(1+x+x^2)\cdots(1+x+x^2+x^3\cdots+x^{n-1})$?

(this is not homework)

-
This is done in George Andrews' book, The Theory Of Partitions. Addison-Wesley, 1976. See also stolaf.edu/people/garrettk/symmetries.pdf and math.ucsd.edu/~aniederm/research1031.pdf and the references thereof. –  Gerry Myerson Dec 10 '11 at 22:32
That's supposed to be $x^3$ in the middle of the last parenthesis? –  joriki Dec 11 '11 at 1:20
yeah, I edited the questions –  Alex M Dec 11 '11 at 2:00
Pick $\sigma_1$. That determines that there will be $\sigma_1-1\in\{0,\dotsc,n-1\}$ inversions involving $\sigma_1$, no matter what other values you will pick. The options you have for inversions involving only the remaining values don't depend on the value of $\sigma_1$ you picked; you can imagine the remaining values "compressed" into the range $\{2,\dotsc,n\}$ by moving the values below $\sigma_1$ up by one to fill the gap; that doesn't change the ordering of the values. So the options remaining are the ones for a permutation of $n-1$ objects. Thus the formula follows by induction, since the options $0,\dotsc,n-1$ for $\sigma_1-1$ add a factor $1+x+\dotso+x^{n-1}$ to the generating function for $S_{n-1}$.