4
$\begingroup$

For $\sigma\in S_n$ an inversion is a pair $(\sigma_i,\sigma_j)$ such that $i 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)

  • 0
    This is done in George Andrews' book, The Theory Of Partitions. Addison-Wesley, 1976. See also http://www.stolaf.edu/people/garrettk/symmetries.pdf and http://www.math.ucsd.edu/~aniederm/research1031.pdf and the references thereof.2011-12-10
  • 1
    That's supposed to be $x^3$ in the middle of the last parenthesis?2011-12-11
  • 0
    yeah, I edited the questions2011-12-11

1 Answers 1

5

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