If $p = p_1 . . . p_n$ is a permutation and an inversion in $p$ is a pair $1 ≤ i < j ≤ n$ such that $j$ appears to the left of $i$ in $p$, how do I prove that $\sum_{p∈S_n}x^{inv(p)} = (1 + x)(1 + x + x^2)· · ·(1 + x + · · · + x^{n−1})$, where $inv(p)$ is the total number of inversions in $p$?
What I got is for each pair $i < j$ the probability of inversion is 1/2 and as there are n(n−1)/2 such pairs, the expected number of inversions is $n(n-1)/4$, but this isn't a statistics problem and doesn't help me in proving the sum, so I'm not sure what to do here
This boils down to induction and picking the last element in the permutation. Suppose this is true for $S_n$, where the series is $P_n(x) $. In $S_{n+1}$, the permutations where $\sigma(n+1)=n+1$ are represented by $P_n(x) $. If $\sigma(n+1)=n$, the first $n$ elements have inversions distributed like $P_n(x) $, but we have one additional inversion, giving us $xP_n(x) $.
In general, if $\sigma(n+1)=k$, the inversions are distributed like $x^{n+1-k}P_n(x)$.