so, I’m taking this combinatorics class. And combinatorics is kind of my thing. But the class definitely puts a lot of learning responsibility on the student. Well, I could just complain and say “I wish we had more psets”. But maybe a more productive thing to do would be to be self-disciplined in working through exercises left in lecture and learning stuff. For this purpose I’m going to write some blog posts corresponding to solutions to the exercises left in lecture.
Anyways, enough talk. Let’s count!
Theorem. \[\sum_{w\in S_n}x^{inv(w)} = \prod_{n\geq 1} \sum_{i=0}^n x^i\]
where inv counts the number of inversions in the permutation
todo: show that this is equidistributed with the majority index
Proof. define the “inversion profile” to be, for each \(i>1,\) we record for how many \(j<i\) \(i,j\) is an inversion, i.e. \(\pi_j>\pi_i\).
This is an invertable procedure: given an inversion profile I can reconstruct the permutation by recursing up from a size \(1\) thing and inserting the next point at the right place each time.
But an inversion profile clearly amounts to choosing powers of \(x\) from the polynomials in the product. So we have the desired bijection.