∆ Definition 1. Consider a permutation $\left( \begin{smallmatrix} 1&2&...&n \\ j_1&j_2&...&j_n \end{smallmatrix} \right)$. A disorder is pair $(k,l)$ with $1\leqslant k< l\leqslant n$ such that $j_k>j_l$. A permutation is called even if the number of disorders is even and odd otherwise.

Problem 1. Find the parity of permutations in Problems 1 and 2 from the problem set Permutations 1. Send a solution

Problem 2. Consider $a=(1, 2, 3, 4)$, $b=(1, 4, 3)$. Which of the following permutations are even and which are odd? 1) $e$; 2) $a$; 3) $b$; 4) $b^2=b\cdot b$; 5) $b^3=b\cdot b\cdot b$; 6) $ab$; 7) $ba$? Send a solution

Problem 3. Show that 1) The multiplication by transposition (from the left or from the right) changes the parity. 2) The parity of a product of $k$ transpositions is equal to the parity of $k$. Send a solution

Problem 4. 1) How to express the parity of $ab$ using the parity of $a$ and the parity of $b$? 2) How to express the parity of $a^n$ using the parity of $a$? Send a solution

Problem 5. Which number is bigger the number of even permutations in $S_n$ or the number of odd permutations in $S_n$? Send a solution

Problem 6. * Show that if in the 15-puzzle we swap the tiles numbered "14" and "15", then we cannot rearrange the puzzle into the initial order. Send a solution

Problem 7. * Suppose we start with a random arrangement of tiles in the 15-puzzle. Show that by sliding the tiles we can either get to the initial arrangement or to the arrangement on the picture above. Send a solution

∆ Definition 2. The inverse of $a\in S_n$ is a permutation $b\in S_n$ such that $ab=ba=e$. Notation: $a^{-1}$.

Problem 8. Show that 1) If $ab=e$, then $b=a^{-1}$ и $a=b^{-1}$. 2) $(a^{-1})^{-1}=a$. Send a solution

Problem 9. Find all $a\in S_n$ such that for any $b\in S_n$ the following is true 1) $ba=b$; 2) $ba=ab$; 3*) $ba=ab^{-1}$. Send a solution

Problem 10. * (Change of variables) Consider $a,c\in S_n$, and let $b=c^{−1}ac$. а) Show that if $a$ is given by $a={\left( \begin{smallmatrix}i_1 \ldots i_n \\ j_1 \ldots j_n\end{smallmatrix}\right)}$, then $b={\left( \begin{smallmatrix} c(i_1) \ldots c(i_n) \\ c(j_1) \ldots c(j_n) \end{smallmatrix}\right)}$. б) Show that if $a$ is given as a product of independent cycles $a = (i_1 \ldots i_k) (j_1 \ldots j_l) \ldots$, then $b=(c(i_1) \ldots c(i_k))(c(j_1)\ldots c(j_l)) \ldots $. Send a solution

Problem 11. Define the degree of permutation $a^k$ for any integer $k$. Send a solution

Problem 12. Show that for any $a,b\in S_n$ and any integers $k$ и $l$, the following if true: 1) $a^0=e\,$; $ a^1=a\,$; $a^{k+l}={a^k}{a^l}\,$; $a^{kl}=(a^k)^l$. 2) If $ab=ba$, then $(ab)^k={a^k}{b^k}$. Send a solution

Problem 13. 1) Show that for any $a,b\in S_n$ there are unique $x,y\in S_n$ such that $ax=b,\,ya=b$. Is it always true that $x=y$? 2) Show that for any $a,b,c\in S_n \\ (a=b)\Longleftrightarrow (ac=bc)\Longleftrightarrow (ca=cb)$. Send a solution

Problem 14. Show that for any permutation $a\in S$ there is a natural number $k$ such that $a^k=e$. Send a solution

∆ Definition 3. The smallest natural number $k$ such that $a^k=e$ for $a\in S$, is called the order of permutation $a$.

Problem 15. Consider permutation $σ$ given by the product of independent cycles $c_1,\ldots, c_n$. Show that the order of permutation $σ$ is equal to the $LCM(|c_1|, …, |c_n|)$ (lowest common multiple), where $|c_i|$ is the length of cycle $c_i$. Send a solution

Problem 16. Let $k$ be the order of permutation $a$. Show that $a^n=e$ if and only if $n$ is divisible by $k$. Send a solution

Problem 17. Compute the following: 1) ${\left( \begin{smallmatrix}1&2&3 \\ 3&2&1\end{smallmatrix}\right)}^{100}$;  2)  ${\left(\begin{smallmatrix} 1&2&3&4 \\ 2&3&4&1\end{smallmatrix}\right)}^{1000}$;  3)  ${\left(\begin{smallmatrix} 1&2&3&4&5 \\ 3&5&2&1&4\end{smallmatrix}\right)}^{-1000}$;  4)  ${\left(\begin{smallmatrix} 1&2&3&4&5 \\ 4&5&2&1&3\end{smallmatrix}\right)}^{500}$;  5)  ${\left(\begin{smallmatrix} 1&2&3&4&5&6 \\ 4&5&2&6&3&1\end{smallmatrix}\right)}^{-127}$;  6)  ${\left(\begin{smallmatrix} 1&2&3&4&5&6&7 \\ 7&6&5&1&2&3&4\end{smallmatrix}\right)}^{1001}$;  Send a solution