1
$\begingroup$

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.

  • 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).2012-03-24
  • 0
    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 in each step, we are able to get the identity permutation. (Take your favorite sorting algorithm to prove this.)2012-03-24
  • 0
    @ArturoMagidin: not exactly equivalent, because he allows only the transpositions that increase the number of inversions.2012-03-24
  • 0
    @darij: Sorry? Since $(ij)=(ji)$, how is it different from "performing a transposition"? He does not specify that if we did $(i_kj_k)$ in the $k$th step, and $(i_{k+1}j_{k+1})$ in the $(k+1)$st step, then it must satisfy $i_k\lt j_k$, $i_{k+1}\lt j_{k+1}$, **and** $i_k\lt i_{k+1}$ (though my argument for why it is true *does* satisfy that condition).2012-03-24
  • 0
    What I got myself is induction proof. But Arturo's observation is quite smart.2012-03-24
  • 0
    @ArturoMagidin: ah, you're right, thanks. I misread his conjecture.2012-03-24
  • 3
    «One can order a shelf of books using two hands, without even a place to temporarily put the books.»2012-03-24
  • 0
    @ablmf: Still true: now, "shuffle" the book you want in the first position down to the first position by exchanging it with the one adjacent to it. Then "shuffle down" the book you want in the second position; then the one that is to end in the third position; etc. You still don't need a place to temporarily put the books... (Equivalent to the statement that $S_n$ is generated by transpositions of the form $(k,k+1)$.)2012-03-24
  • 0
    Now another: show that every permutation of $n$ elements can be expressed as a product of permutations of the form $(1,i)$ with $2\leq i\leq n$; in the "books in a shelf" scenario, you are only allowed to exchange the *first* book with another book.2012-03-24
  • 1
    The 2nd conjecture is that bubble sort works. And it does!2012-03-25

1 Answers 1

1

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 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.

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