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
    I'm not sure I understand your question. Do you mean, is there some ordering of $S_n$ for which there is an "elementary formula" for $f(n,k,i)$, where this represents "the image of $i$ under the $k$th permutation of $S_n$"? (and what does "elementary formula" mean?)2011-11-21
  • 0
    I mean elementary formula in that the image of $i$ under the permutation $\sigma_k$ can be computed without means of ridiculous things like the gamma function, i.e., with elementary functions. And to clarify, I would be fine picking any ordering for which such a formula exists, but I really want to know what the formula is; the grand prize is to have such a formula for all $n$, which is based only on $n, i, k$.2011-11-21
  • 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
    By first element I'm guessing you mean image of 1, but how does that give you a way to find all of the permutation if it's a union of disjoint cycles?2011-11-21
  • 0
    @Bean: No, I was referring to a function $k \to S_n$, viewing the elements of $S_n$ as strings of $n$ naturals in the range $[1,n]$. This is how to get the first entry in the string. Then for the second you use the same function from $k-\lfloor \frac{k}{(n-1)!}\rfloor(n-1)!\to S_{n-1}$ regarding the set as $\{1,2,3,\ldots n\}$ missing the one you already chose.2011-11-21
  • 0
    Should the "floor" be a "1 + floor"? For any $k < (n-1)!$ the first element of the first permutation will be 0...2011-11-21
  • 0
    @Bean: right you are if indexed from $1$. I will clarify.2011-11-21
  • 0
    Sorry but, how does this answer the question? Where is $i$? (Or, have I misunderstood the question?) Moreover, it seems to me that unranking a permutation requires a loop.2011-11-21
  • 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.