2
$\begingroup$

Compute the sum of the number of inversions that appear in the elements of $S_n$. In other words find the total number of inversions that the elements of $S_n$ have combined.

I mean how can we calculate the sum of the inversions if we don't know about the elements present in $S_n$?

$\endgroup$
3
  • 2
    $\begingroup$ What does "the sum of the number of inversions" mean? take $n=2$ or $n=3$...can you write out exactly what you mean? $\endgroup$
    – lulu
    Feb 10, 2016 at 17:20
  • $\begingroup$ I have updated the question. I have no idea about what they want and that is why I am asking here because I am totally blank about it. $\endgroup$
    – max
    Feb 10, 2016 at 17:25
  • 1
    $\begingroup$ I think you should ask whoever posed the question for clarification. Best guess I have, and it is just a guess, is "how many elements of order $2$ are there in $S_n$?". But maybe something else is intended. $\endgroup$
    – lulu
    Feb 10, 2016 at 17:32

3 Answers 3

7
$\begingroup$

Observe that an element $k$ of a permutation of $S_n$ can participate in zero, one, two etc. up to $k-1$ inversions. Hence we obtain the following generating function of permutations of $S_n$ classified according to inversions:

$$G(z) = 1\times (1+z)\times (1+z+z^2)\times\cdots\times (1+z+z^2+\cdots+z^{n-1}).$$

This is

$$G(z) = \prod_{q=0}^{n-1} (1+z+z^2+\cdots +z^q).$$

The total number of inversions is thus given by

$$\left.\frac{d}{dz} G(z)\right|_{z=1} = \left.\prod_{q=0}^{n-1} (1+z+z^2+\cdots +z^q) \sum_{q=0}^{n-1} \frac{1+2z+3z^{2}+\cdots+qz^{q-1}}{1+z+z^2+\cdots +z^q}\right|_{z=1} \\ = n! \sum_{q=0}^{n-1} \frac{1/2 q(q+1)}{q+1} = \frac{1}{2} n! \sum_{q=0}^{n-1} q = \frac{1}{2} n! \frac{1}{2} (n-1) n = \frac{1}{4} n! (n-1) n.$$

This yields for the average number of inversions in a random permutation

$$\frac{1}{4} (n-1) n.$$

The generating function $G(z)$ also appeared at this MSE link.

$\endgroup$
1
  • $\begingroup$ could you please explain why you differentiated the generating function? $\endgroup$
    – Student
    Apr 10, 2017 at 18:38
1
$\begingroup$

Shorter answer:

Given a permutation $\pi\in S_n$, let $X_\pi (i,j)=1$ if $\pi(i)>\pi(j)$ and $0$ otherwise. (That is, $X$ tells whether $i$ and $j$ are inverted in $\pi$.)

Then the number of inversions of $\pi$ is $i_\pi = \displaystyle \sum_{(i,j)} X_\pi (i,j)$, where the sum -- and similar sums below -- are over all $(i,j)$ such that $i,j\in \{1,2,\ldots,n\}$ and $i<j$. The expected value of $i_\pi$ is $${1\over n!}\sum_{\pi} i_\pi = {1\over n!} \sum_\pi \sum_{(i,j)} X_\pi (i,j) = {1\over n!} \sum_{(i,j)} \sum_\pi X_\pi(i,j) = {1\over n!} \sum_{(i,j)} {n!\over 2}= {1\over2}\sum_{(i,j)} 1 = {1\over 2}\cdot {n \choose 2}. $$ Notes:

$\displaystyle\sum_\pi X_\pi(i,j)={n! \over 2}$, because $i$ and $j$ are inverted in exactly half of the permutations.

$\displaystyle\sum_{(i,j)}$ is over exactly $\displaystyle{n\choose 2} = {n(n-1)\over 2}$ ordered pairs.

$\endgroup$
0
$\begingroup$

Shorter answer (:-)

For each permutation $\sigma\in\mathfrak{S}_n$, let's denote by $\text{inv}(\sigma)$ the number of its inversions.

Consider the permutation $c$ defined by :

$$\forall k\in\{1,\ldots,n\},\,c(k)=n+1-k$$

Since $\mathfrak{S}_n\to\mathfrak{S}_n,\sigma\mapsto\sigma\circ c$ is bijective, and since any pair $\{i,j\}$ is an inversion for $\sigma$ iff it's NOT an inversion for $\sigma\circ c$, we have :

$$2\sum_{\sigma\in\mathfrak{S}_n}\text{inv}(\sigma)=\sum_{\sigma\in\mathfrak{S}_n}\left[\text{inv}(\sigma)+\text{inv}(\sigma\circ c)\right]=n!\frac{n(n-1)}2$$ and finally :

$$\boxed{\sum_{\sigma\in\mathfrak{S}_n}\text{inv}(\sigma)=n!\frac{n(n-1)}4}$$

Remark - This proves that the expected value of the number X of inversions of a randomly choosen permutation is : $\mathbb{E}(X)=\frac{n(n-1}4$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .