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


(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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.