Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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? –  JeremyKun Nov 21 '11 at 3:40
    
@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
show 1 more comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.