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.

I made a conjecture today

Start from $1, \ldots, n$, by interchanging the position of $i$ and $j$ where $i < j$ in each step, we are able to get any permutation of $\{1, \ldots, n\}$.

Do you think my conjecture is correct?


OK, it turns out this is very easy. What if we add the following extra constraint to the conjecture?

In each step we can only switch the position of $i$ and $j$ who are adjacent in current permutation.

share|improve this question
3  
Yes, your conjecture is correct. It is equivalent to the statement that the symmetric group $S_n$ is generated by transpositions. Or, to the simple observation that if you want to, say, reorder $n$-books in your shelf, you can do this by exchanging two books at a time (exchange the book currently in position $1$ with the book you want in position $1$; then the book currently in position $2$ with the one you want in position $2$; etc until you are left with just two books, either in order (you are done) or in the wrong place (exchange them). –  Arturo Magidin Mar 24 '12 at 22:32
    
Yes, and you should formulate it "from the end": Start from any permutation of $\left\lbrace 1,2,...,n\right\rbrace$. By interchanging the position of $i$ and $j$ where $i<j$ in each step, we are able to get the identity permutation. (Take your favorite sorting algorithm to prove this.) –  darij grinberg Mar 24 '12 at 22:33
    
@ArturoMagidin: not exactly equivalent, because he allows only the transpositions that increase the number of inversions. –  darij grinberg Mar 24 '12 at 22:33
3  
«One can order a shelf of books using two hands, without even a place to temporarily put the books.» –  Mariano Suárez-Alvarez Mar 24 '12 at 23:03
1  
The 2nd conjecture is that bubble sort works. And it does! –  Louis Mar 25 '12 at 0:03
show 5 more comments

1 Answer

up vote 1 down vote accepted

The easiest way to interpret this problem is as a sorting algorithm.

Take $n$ people and stand them in a line. Tell each person "if the person on your right is taller than you, then swap places".

We eventually will get the tallest person on the left. Then, by induction (ignoring the tallest person), we will get the next-tallest person on his right, and so on, down to the shortest person on the right.

Each swap made takes a taller person on the right and a shorter person on the left. This seems to be where you were heading with the $i<j$ constraint, although, as it stands, it's an empty constraint: e.g. we can interchange the position of $4$ and $2$, since when $i=2$ and $j=4$, we have $i<j$.

Reversing this process shows that we can reach any permutation via transpositions.

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.