# Elementary formula for permutations?

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?

-
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?) – Arturo Magidin Nov 21 '11 at 3:23
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$. – JeremyKun Nov 21 '11 at 3:36
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. – JeremyKun Nov 21 '11 at 3:42

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.
@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. – Ross Millikan Nov 21 '11 at 3:44
Should the "floor" be a "1 + floor"? For any $k < (n-1)!$ the first element of the first permutation will be 0... – JeremyKun Nov 21 '11 at 3:55
@Bean: right you are if indexed from $1$. I will clarify. – Ross Millikan Nov 21 '11 at 4:55
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. – James Nov 21 '11 at 22:32