1
$\begingroup$

For $1 \le i \lt n$, let $m_i$ be the number of inversions $(i,j), i \lt j \le n,$ in permutation $ \sigma$. Let $ \sigma_i = (i+m_i,i+m_i-1)..(i+1,i)$.

How to prove that $\sigma=\sigma_1...\sigma_{n-1}$?

$\sigma$ is a n-permutation.

Inversions of a permutation are the pairs $(i,j)$ such that $1 \le i \lt j \le n$ and $ \sigma (i) \gt \sigma (j)$

  • 0
    Define "inversion," and let us know whether your permutations act on the left or right: Is $(1,2)(2,3)=(1,3,2)$ or $(1,2,3)$? – 2011-11-16
  • 0
    @Thomas: It must be $(1,2,3)$: for the permutation $2431$ OP’s formula yields $(2,1)[(4,3)(3,2)](4,3)$, which has to be evaluated from right to left to make it work. – 2011-11-16
  • 0
    How to prove it? Induct on $n$! – 2011-11-16

0 Answers 0