1
$\begingroup$

Each finite permutation $f$ is product of $2$-cycles of the form $(i,i+1)$, where $1 \leq i < n$.

For example, $(1, 2, 3, 4, 5, 6, 7, 8, 9)= (1,2) \circ (2,3) \circ (3,4) \circ (4,5) \circ (5,6) \circ (6,7) \circ (7,8)$ or $(1,3) = (2,3) \circ (1,2) \circ (2,3)$

This is one of the questions we presented in one session to contest preparation PUTNAM. It turns out that I can't get from the problem. Could someone just give me a hint?

$\endgroup$
1
$\begingroup$

Hint: Induction.

Full solution:

For $n=1,2$ it is straightforward, we call a transposition of the form $(i,i+1)$ a good transposition.

Inductive step: By the hypothesis any permutation that leaves $n+1$ fixed can be obtained as a product of good transpositions. So take a permutation $P$ and write it as a product of disjoint cycles $P=C_1,C_2\dots C_n$ where $C_1$ is the cycle containing $n+1$. Write $C_1$ as $(c_1,c_2\dots c_k,n+1)$. Now notice we can write $(c_1,c_2\dots c_k)$ as a product of good transpositions by the inductive hypothesis. From here we notice $(c_1,c_2\dots c_k)(c_k,n+1)=(c_1,c_2\dots c_k,n+1)=C_1$. So if we see $(c_k,n+1)$ is a product of good transpositions we are done. By the inductive hypothesis $(c_k,n)$ is a product of good transpositions. Now notice $(n,n+1)(c_k,n)(n,n+1)=(c_k,n+1)$. So $C_1$ can be written as a product of good transpositions . And by the inductive hypothesis $C_2,C_3\dots C_n$ can be written also. Therefore their product $C_1C_2\dots C_n=P$ is also a product of good transpositions and we are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy