Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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
1  
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

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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