Цикли і транспозиції. Подібні підстановки.

Множина підстановок степеня n, із зазначеною операцією множення, є групою. Ця група позначається і називається симетричною групою -ой степеня. Порядок групи дорівнює .

Підстановкою називається взаємно однозначне відображення скінченної множини на себе.

Звичайно підстановки записують у виді двох рядків. Верхній рядок є операндом підстановки, а нижня - результатом її дії на операнд.

Наприклад, .

Елементи скінченної множини завжди можна перенумерувати, отже, операнд будь-якої підстановки можна записати у виді 1 2... n, де n - кількість елементів в операнде: (т. зв. запис підстановки в канонічному виді).

Число n називається степенем підстановки.

Результат послідовної дії підстановок називається їхнім добутком і записується .

Добуток двох підстановок визначається виходячи з того, що якщо перша підстановка переводить j на місце i, а друга підстановка, переводить k на місце j, те в добутку k переходить на місце i.

Таким чином, якщо , , , те , наприклад, при і , .

Легко бачити, що , однак дужки в добутках можна розставляти довільно. Існує «одинична» підстановка I, така, що для всіх T : IT=TI=T. Для нашого прикладу .

Для будь-якої підстановки існує обернена підстановка , така, що . Для побудови досить переставити місцями рядка в підстановці , а потім упорядкувати стовпчика так, щоб числа у верхньому рядку йшли у зростаючому порядку.

У деякому розумінні, підстановки степеня n можуть бути сконструйовані з підстановок меншого степеня.

Справа в тім, що підстановки степеня n<N можуть діяти на операнде з N елементів, якщо вважати, що кожний з N-n додаткових елементів не переміщується (переходять у себе). Наприклад, при доповненні кожного операнда елементами n+1, n+2 ... N, можна вважати, що = .

Виходячи з цього, можна говорити про те, що підстановки меншого степеня включаються у множину підстановок більшого степеня і, у свою чергу, утворюють підгрупу групи .

Кожну підстановку Т можна представити у виді добуткуT= деяких спеціальних підстановок, що називаються циклами, причому, цикли попарно незалежні. Останнє означає, що підстановки і , при , якщо не брати до уваги елементи, які залишаються нерухомими, діють на підмножинах операнда підстановки Т, що не перетинаються.

Нехай 1<k<n і Р - підстановка степеня n, причому Р¹I. Підстановка Р називається k-членним циклом, якщо вона не переміщає N-k елементів, а її дію на решту k елементів: можна представити у вигляді циклічної діаграми переходів: . У цій діаграмі дозволяється тільки один перехід від елемента з більшим індексом, до елемента з меншим індексом, а саме: .

Наприклад, тричленний цикл п'ятого степеня: . Тут елементи 4 і 5 нерухомі, причому , , .

Циклічна діаграма переходів, може бути виписана, починаючи з будь-якого свого елемента. Цикл записують у виді, аналогічному діаграмі переходів: . Одиничну підстановку розглядають як добуток одночленних циклів виду .

Для запису підстановки у вигляді добутку незалежних циклів досить виписати всі різні діаграми переходів. Наприклад, підстановка може бути представлена як . Одночленні цикли при такому записі часто ігноруються.