1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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