∆ Определение 1. Пусть дана подстановка $\left( \begin{smallmatrix} 1&2&...&n \\ j_1&j_2&...&j_n \end{smallmatrix} \right)$. Беспорядком называется пара $(k,l)$  $1\leqslant k< l\leqslant n$, такая что $j_k>j_l$. Подстановка называется чётной, если число беспорядков в ней чётно и нечётной — в противном случае.

Задача 1. Найдите чётности подстановок из задач 1 и 2 предыдущего листка. Отправить решение

Задача 2. Пусть $a=(1, 2, 3, 4)$, $b=(1, 4, 3)$. Какие из следующих подстановок чётны, а какие нечётны: 1) $e$; 2) $a$; 3) $b$; 4) $b^2=b\cdot b$; 5) $b^3=b\cdot b\cdot b$; 6) $ab$; 7) $ba$? Отправить решение

Задача 3. 1) При умножении на транспозицию (справа или слева) чётность меняется. 2) Чётность произведения $k$ транспозиций равна чётности числа $k$. Отправить решение

Задача 4. 1) Как выражается чётность $ab$ через чётность $a$ и чётность $b$? 2) Как выражается чётность $a^n$ через чётность $a$? Отправить решение

Задача 5. Каких подстановок в $S_n$ больше: чётных или нечётных? Отправить решение

Задача 6. * Докажите, что если в игре "пятнашки" поменять местами фишки с номерами "14" и "15", то, играя в эту игру, невозможно получить первоначальное расположение фишек. Отправить решение

Задача 7. * Докажите, что из любого расположения фишек можно, соблюдая правила игры, получить либо начальное расположение, либо расположение, описанное в предыдущей задаче. Отправить решение

∆ Определение 2. Подстановкой, обратной к подстановке $a\in S_n$ называется такая подстановка $b\in S_n$, что $ab=ba=e$. Обозначение: $a^{-1}$.

Задача 8. Докажите, что: 1) Если $ab=e$, то $b=a^{-1}$ и $a=b^{-1}$. 2) $(a^{-1})^{-1}=a$. Отправить решение

Задача 9. Найдите все $a\in S_n$ такие, что для любой подстановки $b\in S_n$ выполняются равенства: 1) $ba=b$;  2) $ba=ab$;  3*) $ba=ab^{-1}$. Отправить решение

Задача 10. * (замена переменных) Пусть даны подстановки $a, c∈S_n$, и пусть $b=c^{−1}ac$. а) Докажите, что если подстановка $a$ задана таблицей $a={\left( \begin{smallmatrix}i_1 \ldots i_n \\ j_1 \ldots j_n\end{smallmatrix}\right)}$, то $b={\left( \begin{smallmatrix} c(i_1) \ldots c(i_n) \\ c(j_1) \ldots c(j_n) \end{smallmatrix}\right)}$ б) Докажите, что если подстановка $a$ задана в виде произведения независимых циклов $a = (i_1 \ldots i_k) (j_1 \ldots j_l) \ldots$, то $b=(c(i_1) \ldots c(i_k))(c(j_1)\ldots c(j_l)) \ldots $. Отправить решение

Задача 11. Дайте определение степени подстановки $a^k$ для любого целого $k$. Отправить решение

Задача 12. Докажите, что для любых $a,b\in S_n$ и любых целых $k$ и $l$ выполняется следующее: 1) $a^0=e\,; $ $ a^1=a\,; $ $a^{k+l}={a^k}{a^l}\,; $ $a^{kl}=(a^k)^l;$ 2) Если $ab=ba$, то $(ab)^k={a^k}{b^k}$. Отправить решение

Задача 13. 1) Докажите, что для любых $a,b\in S_n$ существуют и при том единственные $x,y\in S_n$ такие, что $ax=b,\,ya=b$. Обязательно ли $x=y$? 2) Докажите, что для любых $a,b,c\in S_n \\ (a=b)\Longleftrightarrow (ac=bc)\Longleftrightarrow (ca=cb)$. Отправить решение

Задача 14. Докажите, что для любой подстановки $a\in S_n$ существует натуральное $k$ такое, что $a^k=e$. Отправить решение

∆ Определение 3. Наименьшее натуральное $k$, такое, что для подстановки $a\in S_n$ выполняется равенство $a^k=e$, называется порядком подстановки $a$.

Задача 15. Пусть подстановка $σ$ представлена в виде произведения независимых циклов $c_1,\ldots, c_n$. Докажите, что порядок подстановки $σ$ равен $НОК(|c_1|, …, |c_n|)$ (где $|c_i|$ есть длина цикла $c_i$). Отправить решение

Задача 16. Если $k$ — порядок подстановки $a$, то $a^n=e$ тогда и только тогда, когда $n$ делится на $k$. Отправить решение

Задача 17. Вычислить: 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}$;  Отправить решение