## Interesting Combinatorial Sum Involving Inversions

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

where and is the number of inversions of a permutation. In doing so we find an interesting way to prove that .

**Theorem: **Let , then

**Proof: **We proceed by induction. For we see that and thus

as claimed. Next, suppose that this is true for . Consider then is partitioned into two blocks: those which fix and those that don’t, call these blocks and respectively. Identify each element of with its associated -tuple. Notice then that the elements of are of the form and the elements of are of the form . For each element of the associated -tuple can be thought of as the association of an -tuple with an element of with the addition of the last coordinate, always being . In particular, the elements of are precisely the permutation of the form such that and in particular . It evidently follows then that

Next note that if and the associated -tuple is

Then, if one removes the coordinate which resides in then the resulting tuple can be uniquely identified with an element of . Moreover, if is that associated permutation then . It follows then that for each fixed we call all the elements of of the form then

and thus noticing that

it follows that

So, we may conclude that

and the induction is complete.

From this we get an interesting way to prove that . Indeed, letting in the above gives

No comments yet.

## Leave a Reply