Abstract Nonsense

Crushing one theorem at a time

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!

Advertisements

December 27, 2010 - Posted by | Computations, Fun Problems, Group Theory | , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: