Подстановки

Пусть Х – конечное множество, Х = {х₁, х₂,…, х_n }. Группу подстановок S(X) в этом случае мы будем обозначать S_n. Подстановку s множества Х можно записывать в виде таблицы s = , где в нижней строке стоят каким-то образом переставленные элементы множества Х. Такая таблица означает, что s(х₁)= , s(х₂)= , s(х₃)=…

Так как s - инъекция, то все элементы нижней строки различные. Так как s - сюръекция, то в нижней строке присутствуют все элементы множества Х. То есть, нижняя строка – это перестановка множества Х. Таким образом, различных подстановок существует ровно столько, сколько имеется различных перестановок множества Х, то есть n!, и, значит, группа S_n подстановок множества из п элементов состоит из n! элементов.

Упражнение. Доказать, что для конечного множества Х

из инъективности s следует её сюръективность, а из сюръективности - инъективность.

Чаще всего мы будем считать, что Х = {1, 2, 3, …, n }. В этом случае подстановки мы будем записывать в виде

s =, где i₁, i₂,…, i_n - перестановка чисел 1, 2, 3, …, п.

Для композиции подстановок s₁s₂ вначале выполняется подстановка s₂, а затем s₁, а для композиции s₁*s₂ - вначале s₁, а затем s₂.

Пусть s ^k =s s …s - произведение k множителей. Так как Х - конечное множество, то " xÎ Х "s Î S_n {s ^kx | kÎ N } – конечное подмножество в Х, то есть $ k¹ m такие, что s ^k x = s ^m x. Тогда, если k> m, то, очевидно,

s ^k-m x = x. Пусть s – наименьшее натуральное число такое, что s ^sx = x. Тогда подмножество {x, s x, s ²x, s ³x,…,s ^s-1x} будем называть циклом, порожденным элементом х, и обозначать O(х). Очевидно, все элементы в O(х) – различны, то есть O(х) состоит из s элементов. Будем считать, что по определению s ⁰ = id, s⁰x= х.

Дата добавления: 2014-01-04