1

I've found in a paper the formula for the lexicographical order of a permutation, but I didn't find anywhere a proof for it.

For example, we have the following set $S=\{1, 2,3\}$. We have $3! = 6$ permutations: $$\sigma_1 =(1, 2, 3) \\ \sigma_2 =(1, 3, 2) \\ \sigma_3 =(2, 1, 3) \\ \sigma_4 =(2, 3, 1) \\ \sigma_5 =(3, 1, 2) \\ \sigma_6 =(3, 2, 1)$$

Let's define the function $N(\sigma) =$ lexicographical order of the permutation $\sigma$. For example, $N(\sigma_5) = 5$, because $\sigma_5$ permutation is the 5th permutation in the lexicographical order.

Let's define another function $inv_\sigma(i) =$ the number of inversions for the i-th position in the permutation $\sigma$ (basically, for a specific $i$, $inv_\sigma(i) =$ how many smaller number then $\sigma(i)$ are after $i$-th position). For the sake of example, we have the following permutation and $inv_{\sigma^\prime}(i)$ function: $$\sigma^\prime = (1,3,5,2,6,4)\\ inv_{\sigma^\prime}(i)=(0,1,2,0,1,0) $$

The formula for $N(\sigma) = 1 + \sum_{i = 1}^{n} inv_\sigma(i)(n - i)!$, where $n$ is the lenght of ther permutation.

andrei81
  • 65
  • That can't be the length of a permutation $\sigma\in S_n$, defined as the degree $n$ (of the usual permutation action of $S_n$) minus the number of orbits of $\sigma$, or equivalently the smallest number of transpositions needed to represent $\sigma$. – user10354138 Mar 18 '21 at 06:32
  • 1
    Anyway, just induct. There are $\operatorname{inv}\sigma(1)$ choices of where $1$ gets sent to before you get to any permutations that sends $1$ to $\sigma(1)$, and each choice has $(n-1)!$ where to send $2,3,\dots,n$. Then when you start with $1\mapsto\sigma(1)$ there are $\operatorname{inv}\sigma(2)$ choices of where $2$ goes before you get to $\sigma(2)$, and each gives $(n-2)!$ where to send $3,4,\dots,n$, etc. – user10354138 Mar 18 '21 at 06:38

0 Answers0