Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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)
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}$.
