# Abstract Nonsense

## Interesting Combinatorial Sum Involving Inversions

Point of post: In this post we’ll solve the compute sum

$\displaystyle \sum_{\pi\in S_n}q^{\text{inv}(\pi)}$

where $q\in\mathbb{C}$ and $\text{inv}(\pi)$ is the number of inversions of a permutation. In doing so we find an interesting way to prove that $\#\left(S_n\right)=n!$.

Theorem: Let $n\in\mathbb{N},\text{ }n\geqslant 2$, then

$\displaystyle \sum_{\pi\in S_n}q^{\text{inv}(\pi)}=\prod_{k=1}^{n}\sum_{r=0}^{k-1}q^r$

Proof: We proceed by induction. For $n=2$ we see that $S_2=\{\text{id}_{[2]},(1,2)\}$ and thus

\displaystyle \begin{aligned}\sum_{\pi\in S_2}q^{\text{inv}(\pi)} &= q^{\text{inv}(\text{id}_{[2]})}+q^{\text{inv}((1,2))}\\ &= q^0+q^1\\ &= 1+q\end{aligned}

as claimed. Next, suppose that this is true for $n$. Consider then $S_{n+1}$ is partitioned into two blocks: those which fix $n+1$ and those that don’t, call these blocks $B_1$ and $B_2$ respectively. Identify each element of $S_{n+1}$ with its associated $n+1$-tuple. Notice then that the elements of $B_1$ are of the form $(\ast,\cdots,\ast,n+1)$ and the elements of $B_2$ are of the form $(\ast,\cdots,\ast,n+1,\cdots,\ast)$. For each element of $B_1$ the associated $n+1$-tuple can be thought of as the association of an $n$-tuple with an element of $S_n$ with the addition of the last coordinate, always being $n+1$. In particular, the elements of $B_1$ are precisely the permutation of the form $\sigma:[n+1]\to[n+1]$ such that $\sigma_{\mid [n]}\in S_n$ and in particular $\text{inv}(\sigma)=\text{inv}\left(\sigma_{\mid [n]}\right)$. It evidently follows then that

$\displaystyle \sum_{\pi\in B_1}q^{\text{inv}(\pi)}=\sum_{\pi\in S_n}q^{\text{inv}(\pi)}$

Next note that if $\sigma\in B_2$ and the associated $n+1$-tuple is

$(\underbrace{\ast,\cdots,\ast}_{\ell},n+1,\cdots,\ast)\quad\mathbf{(1)}$

Then, if one removes the coordinate which $n+1$ resides in then the resulting tuple can be uniquely identified with an element of $S_n$.  Moreover, if $\pi$ is that associated permutation then $\text{inv}(\sigma)=\text{inv}(\pi)+\ell$. It follows then that for each fixed $\ell$ we call $B_{2,\ell}$ all the elements of $B_2$ of the form $\mathbf{(1)}$ then

$\displaystyle \sum_{\pi\in B_{2,\ell}}q^{\ell}\sum_{\pi\in S_n}$

and thus noticing that

$B_2=B_{2,1}\sqcup\cdots\sqcup B_{2,n}$

it follows that

$\displaystyle \sum_{\pi\in B_2}q^{\text{inv}(\pi)}=\sum_{\ell=1}^{n}q^{\ell}\sum_{\pi\in S_n}q^{\text{inv}(\pi)}$

So, we may conclude that

\displaystyle \begin{aligned}\sum_{\pi\in S_{n+1}}q^{\text{inv}(\pi)} &= \sum_{\pi\in B_1}q^{\text{inv}(\pi)}+\sum_{\pi\in B_2}q^{\text{inv}(\pi)}\\ &= \sum_{\pi\in S_n}q^{\text{inv}(\pi)}+\sum_{\ell=1}^{n}q^{\ell}\sum_{\pi\in S_n}q^{\text{inv}(\pi)}\\ &= \left(\sum_{\pi\in S_n}q^{\text{inv}(\pi)}\right)\left(\sum_{\ell=0}^{n}q^\ell\right)\\ &= \left(\prod_{k=1}^{n}\sum_{r=0}^{n-1}q^r\right)\left(\sum_{r=0}^{n}q^r\right)\\ &= \prod_{k=1}^{n+1}\sum_{r=0}^{k-1}q^r\end{aligned}

and the induction is complete. $\blacksquare$

From this we get an interesting way to prove that $\#\left(S_n\right)=n!$. Indeed, letting $q=1$ in the above gives

$\displaystyle \sum_{\pi\in S_n}1=\prod_{k=1}^{n}k=n!$