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

UptoLike

ВУЗ: 

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

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

Рубрика: 

176 Теория перестановок Гл. 3
Пример 18.2. При возведении цикла в степень он может распа-
даться в произведение циклов меньшей длины:
σ = (2, 8, 6, 4, 1, 5) ∈ S
8
;
σ =
µ
1 2 3 4 5 6 7 8
5 8 3 1 2 4 7 6
;
σ
2
=
µ
1 2 3 4 5 6 7 8
2 6 3 5 8 1 7 4
= (1, 2, 6)(4, 5, 8);
σ
−2
=
µ
1 2 3 4 5 6 7 8
6 1 3 8 4 2 7 5
= (1, 6, 2)(4, 8, 5).
18.4. Вычисление порядка перестановки с помощью ее
разложения на независимые циклы. Всякую перестановку ϕ ∈
S
n
можно (согласно теореме 17.1) разложить в произведение неза-
висимых циклов (17.5). Это разложение позволяет легко вычислить
порядок o(ϕ).
Предложение 18.4. Порядок перестановки ϕ ∈ S
n
, заданной
своим разложением на независимые циклы (17.5), равен наименьше-
му общему кратному длин этих циклов:
o(ϕ) = НОК(s
1
, s
2
, . . . , s
m
), (18.17)
где s
j
— длина цикла σ
j
(j = 1, ..., m).
Доказательство. Прежде всего вы должны четко представлять
себе, что такое наименьшее общее кратное (НОК) двух и несколь-
ких натуральных чисел. Если это не совсем так, то немедленно про-
читайте параграф, посвященный арифметике целых чисел в книге
[2] (или [1]). Напомним также, что в предисловии имеется краткая
сводка соответствующего материала.
Пусть
q = НОК(s
1
, s
2
, . . . , s
m
), (18.18)
т. е., во-первых, q делится на каждое из чисел s
j
(j = 1, ..., m), дру-
гими словами, является общим кратным этих чисел, и во-вторых, q
делит любое общее кратное чисел s
j
.
Пусть G
j
(j = 1, ..., m) — орбиты для перестановки ϕ, т. е. мно-
жества номеров, входящих в независимые циклы σ
j
. (Для нетриви-
альных циклов эти множества совпадают с их областями действия.)
176                         Теория перестановок                              Гл. 3

  Пример 18.2. При возведении цикла в степень он может распа-
даться в произведение циклов меньшей длины:

                             σ = (2, 8, 6, 4, 1, 5) ∈ S8 ;
                            µ                            ¶
                                1 2       3 4 5 6 7 8
                    σ=                                      ;
                                5 8       3 1 2 4 7 6
                µ                                ¶
                  1    2     3 4      5    6 7 8
         σ2 =                                      = (1, 2, 6)(4, 5, 8);
                  2    6     3 5      8    1 7 4
                 µ                                ¶
                   1   2      3   4 5       6 7 8
        σ −2   =                                    = (1, 6, 2)(4, 8, 5).
                   6   1      3   8 4       2 7 5

  18.4. Вычисление порядка перестановки с помощью ее
разложения на независимые циклы. Всякую перестановку ϕ ∈
Sn можно (согласно теореме 17.1) разложить в произведение неза-
висимых циклов (17.5). Это разложение позволяет легко вычислить
порядок o(ϕ).
   Предложение 18.4. Порядок перестановки ϕ ∈ Sn , заданной
своим разложением на независимые циклы (17.5), равен наименьше-
му общему кратному длин этих циклов:

                           o(ϕ) = НОК(s1 , s2 , . . . , sm ),               (18.17)

где sj — длина цикла σj (j = 1, ..., m).
   Доказательство. Прежде всего вы должны четко представлять
себе, что такое наименьшее общее кратное (НОК) двух и несколь-
ких натуральных чисел. Если это не совсем так, то немедленно про-
читайте параграф, посвященный арифметике целых чисел в книге
[2] (или [1]). Напомним также, что в предисловии имеется краткая
сводка соответствующего материала.
   Пусть
                      q = НОК(s1 , s2 , . . . , sm ),     (18.18)
т. е., во-первых, q делится на каждое из чисел sj (j = 1, ..., m), дру-
гими словами, является общим кратным этих чисел, и во-вторых, q
делит любое общее кратное чисел sj .
   Пусть Gj (j = 1, ..., m) — орбиты для перестановки ϕ, т. е. мно-
жества номеров, входящих в независимые циклы σj . (Для нетриви-
альных циклов эти множества совпадают с их областями действия.)

Страницы