Showing Mahonian triangle numbers related to inversion probability

Question

From this OEIS page about Triangle of Mahonian numbers:

http://oeis.org/search?q=+A008302&language=english&go=Search

I know 2 things:

1. That the $T(n,k)$ can be generated by the coefficients in expansion of $$\prod_{i=0..n-1} (1 + x + ... + x^i)$$, where $k$ ranges from $0$ to A000217(n-1).

2. $T(n,k) :=$ number of permutations of $\{1,\ldots,n\}$ with $k$ inversions.

But can you please connect these two distinct ideas, i.e. why would the coefficients of this product of polynomials give the number of inversions of a set of consecutive integers? How are these two things related?

Answer 1

When you multiply $$\prod _{i=0}^{n-1} \sum _{j=0}^i x^j=1(1+x)\cdots (1+x+\cdots +x^{n-1}),$$ what you get as coefficient of $x^k$ is $|\{(a_1,\cdots , a_n):a_i<i \wedge \sum a_i = k\}|$ because of Cauchy product(i.e., $$(\sum _{i=0}^n a_i x^i)(\sum _{i=0}^m a_i x^i)=\sum _{ i = 0}^{n+m}(\sum _{\substack{r+s=i\\ r\leq n\\ s\leq m}}a_rb_s)x^i$$)
Now take a permutation $\pi\in S_n$ with $k$ inversions and denote $A_i = |\{j:j<i \wedge \pi _i < \pi _j\}|,$ so $\sum A_i = k,$ because you are doing a partition of the inversion pairs and $A_i<i$ because $0\leq j<i.$
Hope it helps.

Answer 2

To give a more intuitive and less strict approach:

Claim: There is a bijection with permutations of length $n$ and $n$-tuples $(c[1], c[2], \dots, c[n])$, with $0 \le c[i] \le n - i$ for each $i$.

For each permutation $(p[1], p[2], \dots, p[n])$, let's assign $(c[1], c[2], \dots, c[n])$, where $c[i] = \#\{j > i: p[i] > p[j]\}$. In other words, $c[i]$ counts number of inversions with $i$ being the first member of the pair. Note the property of this tuple: $c[i] \le n - i$ (as there are only $n-i$ other members to it's right). Let's call tuples that satisfy $0 \le c[i] \le n - i$ valid.

Crucial idea is that we can uniquely go in a reverse direction too: for a given valid n-tuple, there's a unique permutation that corresponds to it (easy to prove by construction recursively).

This means there's a bijection, and the number we're looking for is same as the number of valid tuples. Now let's use generating functions to count this: for each $i$, define $G[i](x) = \sum _ {j = 0}^{n - i} x^j$. Multiplying all $G[i]$'s with each other and finding coefficient of $x^k$ gives the desired quantity. (Note that after multiplying all $G[i]$ and rearranging terms, we get the same product as mentioned in the question above).