3
$\begingroup$

Suppose I fix $n$ and let $\sigma_k$ represent the $k$th permutation of $S_n$ with respect to some ordering (whatever ordering might serve my purpose). Is there an elementary formula for $\sigma_k(i)$ which requires only $i, k,$ and $n$?

Is one known for small $n$, perhaps even as small as 4?

  • 0
    Of course, I could imagine there are multiple formulas based on different orderings (if one exists, why not many?), which is why I'm saying pick any ordering you like.2011-11-21

2 Answers 2

6

It depends upon what you mean by elementary. If the ordering is lexicographic, the first element of the $k^{\text(th)}$ permutation of $S_n$ is $\lfloor \frac{k}{(n-1)!}\rfloor$ (assuming the first element of the set is $0$).This leads to an easy recursive function to find the whole $k^{\text(th)}$ permutation.

  • 0
    @James: This formula lets you find the whole permutation. So $\sigma_k(0)=0$ for $k \lt (n-1)!, \sigma_k(0)=1$ for $(n-1)! \le k \lt 2(n-1)!$ and so on. Then to find $\sigma_k(1)$ you use the same approach with $n \to n-1, k \to k-\lfloor \frac{k}{(n-1)!}\rfloor(n-1)! This is described a bit more in http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order$2011-11-21
4

The magic words are "ranking permutations"; see for example Wilf's lecture notes.