Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 165 стр.

UptoLike

ВУЗ: 

ИвГУ | Иваново

Составители: 

Рубрика: 

§
§
§ 17 Разложение перестановки на независимые циклы 165
где "в первой зоне" показаны "реально переставляемые" по цик-
лу номера (s штук), а во "второй зоне" — "неподвижные" номера
(оставшиеся n − s штук). Перестановка (17.3) называется (частич-
ным) циклом длины s; перестановку (17.2) можно назвать полным
циклом длины n.
Замечание 17.1. Обозначения (17.2) и (17.3) называются одност-
рочной записью для циклов.
С этими обозначениями связан ряд условностей.
Например, цикл (5, 1, 4) ∈ S
6
является перестановкой вида
(5, 1, 4) =
µ
1 2 3 4 5 6
4 2 3 5 1 6
,
где квадратиками выделены реально переставляемые номера. Цикл
(5, 1, 4) ∈ S
8
выглядит аналогично, но с добавлением еще двух непо-
движных номеров (7 и 8).
Таким образом, однострочная запись цикла определяет его одно-
значно, если задана степень перестановки (не меньшая наибольшего
из участвующих в цикле номеров).
Другая особенность: записи (5, 1, 4), (1, 4, 5) и (4, 5, 1) определяют
один и тот же цикл.
В общем виде правило выражается так: цикл (17.3) можно начи-
нать с любого i
k
(k = 1, ..., s), т. е.
(i
1
, i
2
, . . . , i
s
) = (i
k
, i
k+1
, . . . , i
s
, i
1
, i
2
, . . . , i
k− 1
).
Определение 17.2. Цикл длины 2 называется транспозицией.
Общий вид транспозиции:
τ = (i
1
, i
2
), (17.4)
где i
1
6= i
2
, причем, в силу замечания 17.1,
τ = (i
1
, i
2
) = (i
2
, i
1
).
Замечание 17.2. Как определить цикл длины 1, который следо-
вало бы обозначить (i
1
)?
Это, очевидно, — тождественная перестановка ε (ибо она должна
оставлять неподвижными как номер i
1
, так и все остальные номера).
Такие циклы мы будем называть тривиальными и будем выбрасы-
вать их (без ущерба для истинности формул). Обратим, однако,
внимание на то, что область действия цикла (i
1
) пуста, а отнюдь не
совпадает с одноэлементным множеством {i
1
}.
§ 17    Разложение перестановки на независимые циклы                                         165

где "в первой зоне" показаны "реально переставляемые" по цик-
лу номера (s штук), а во "второй зоне" — "неподвижные" номера
(оставшиеся n − s штук). Перестановка (17.3) называется (частич-
ным) циклом длины s; перестановку (17.2) можно назвать полным
циклом длины n.
  Замечание 17.1. Обозначения (17.2) и (17.3) называются одност-
рочной записью для циклов.
  С этими обозначениями связан ряд условностей.
  Например, цикл (5, 1, 4) ∈ S6 является перестановкой вида
                          µ                      ¶
                            1 2 3 4        5 6
              (5, 1, 4) =                          ,
                            4 2 3 5        1 6
где квадратиками выделены реально переставляемые номера. Цикл
(5, 1, 4) ∈ S8 выглядит аналогично, но с добавлением еще двух непо-
движных номеров (7 и 8).
   Таким образом, однострочная запись цикла определяет его одно-
значно, если задана степень перестановки (не меньшая наибольшего
из участвующих в цикле номеров).
   Другая особенность: записи (5, 1, 4), (1, 4, 5) и (4, 5, 1) определяют
один и тот же цикл.
   В общем виде правило выражается так: цикл (17.3) можно начи-
нать с любого ik (k = 1, ..., s), т. е.
            (i1 , i2 , . . . , is ) = (ik , ik+1 , . . . , is , i1 , i2 , . . . , ik−1 ).
   Определение 17.2. Цикл длины 2 называется транспозицией.
   Общий вид транспозиции:
                                         τ = (i1 , i2 ),                                    (17.4)
где i1 6= i2 , причем, в силу замечания 17.1,
                                 τ = (i1 , i2 ) = (i2 , i1 ).
   Замечание 17.2. Как определить цикл длины 1, который следо-
вало бы обозначить (i1 )?
   Это, очевидно, — тождественная перестановка ε (ибо она должна
оставлять неподвижными как номер i1 , так и все остальные номера).
Такие циклы мы будем называть тривиальными и будем выбрасы-
вать их (без ущерба для истинности формул). Обратим, однако,
внимание на то, что область действия цикла (i1 ) пуста, а отнюдь не
совпадает с одноэлементным множеством {i1 }.

Страницы