Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 8 стр.

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

3) Под ста нов ка на зы ва ет ся чет ной, ес ли об щее чис ло ин вер сий
в ее стро ках (пе ре ста нов ках) чет но, и не чет ной — в про тив ном слу чае.
Ин вер сию об ра зу ют два чис ла в пе ре ста нов ке, ко гда мень шее
из них рас по ло же но пра вее боль ше го. Для ка ж до го из чи сел оп ре де ля ет -
ся ко ли че ст во стоя щих правее его меньших чисел.
При мер: рас смот рим под ста нов ку:
4 2 5 1 3 6
5 3 1 4 2 6
æ
è
ç
ç
ö
ø
÷
÷
.
Это не чет ная под ста нов ка, так как ко ли че ст во ин вер сий в верх -
ней под ста нов ке: 3 + 1 + 2 + 0 + 0 + 0 = 6; в ниж ней под ста нов ке: 4 + 2 +
+ 0 + 1 + 0 + 0 = 7. Об щее чис ло ин вер сий: 6 + 7 = 13.
4) Вся кую под ста нов ку мож но раз ло жить в про из ве де ние цик лов.
Цикл — это та кая под ста нов ка
( )
a a a a a a
a a a a a a
a a a
1
2
1 1
2 3
1 1
1
2
K K
K K
K
k
k
k
n
k
k
n
k
- +
+
æ
è
ç
ç
ö
ø
÷
÷
=
,
ко то рая пе ре во дит
a
1
в
a
2
,
a
2
в
a
3
, … ,
a
k-1
в
a
k
и
a
k
в
a
1
, а ос таль ные
эле мен ты
a
k+1
…
a
n
пе ре хо дят са ми в се бя. За пись (
a
1
a
2
…
a
k
) — это пе -
ре чис ле ние мно же ст ва эле мен тов, ко то рые цик ли че ски пе ре хо дят друг
в дру га, а ко ли че ст во этих эле мен тов оп ре де ля ет дли ну (по ря док) цик ла.
При мер:
( )( )( )
4 2 5 1 3 6
5 3 1 4 2 6
4 5 1 2 3 6
æ
è
ç
ç
ö
ø
÷
÷
= , , ,
.
Ес ли цикл со сто ит из од ной циф ры (6), то его мож но не за пи сы -
вать. Под ста нов ка, все n эле мен тов ко то рой об ра зу ют цикл, на зы ва ет ся
кру го вой или цик ли че ской.
Цикл дли ны 2 на зы ва ет ся транс по зи ци ей (два эле мен та). Вся кая
под ста нов ка мо жет быть пред став ле на про из ве де ни ем транспозиций:
1 2 3 4 5
2 5 4 1 3
1 2 3 4 5
2 1 3 4 5
2 1 3 4 5
2 5 3 4 1
æ
è
ç
ç
ö
ø
÷
÷
=
æ
è
ç
ç
ö
ø
÷
÷
×
æ
è
ç
ç
ö
ø
÷
÷
×
×
æ
è
ç
ç
ö
ø
÷
÷
×
æ
è
ç
ç
ö
ø
÷
÷
=
2 5 3 4 1
2 5 4 3 1
2 5 4 3 1
2 5 4 1 3
1 2( , ) ( , ) ( , ) ( , )× × ×1 5 3 4 1 3
8
       3) Подстановка называется четной, если общее число инверсий
в ее строках (перестановках) четно, и нечетной — в противном случае.
       Инверсию образуют два числа в перестановке, когда меньшее
из них расположено правее большего. Для каждого из чисел определяет-
ся количество стоящих правее его меньших чисел.

                                           æ4 2 5 1 3 6ö
      Пример: рассмотрим подстановку: çç                    ÷÷ .
                                           è5 3 1 4 2 6ø
      Это нечетная подстановка, так как количество инверсий в верх-
ней подстановке: 3 + 1 + 2 + 0 + 0 + 0 = 6; в нижней подстановке: 4 + 2 +
+ 0 + 1 + 0 + 0 = 7. Общее число инверсий: 6 + 7 = 13.

     4) Всякую подстановку можно разложить в произведение циклов.
Цикл — это такая подстановка

        æa1    a 2 K a k -1      ak   a k +1 K a n ö
        ç                                            ÷ = ( a 1 a 2 K a k ),
        ça     a3 K       ak     a1   a k + 1 K a n ÷ø
        è 2

которая переводит a 1 в a 2 , a 2 в a 3 , … , a k -1 в a k и a k в a 1 , а остальные
элементы a k +1 … a n переходят сами в себя. Запись (a 1 a 2 … a k) — это пе-
речисление множества элементов, которые циклически переходят друг
в друга, а количество этих элементов определяет длину (порядок) цикла.

      Пример:

                   æ4 2 5 1 3 6ö
                   çç           ÷÷ = ( 4, 5, 1) ( 2, 3) ( 6).
                    è5 3 1 4 2 6ø

      Если цикл состоит из одной цифры (6), то его можно не записы-
вать. Подстановка, все n элементов которой образуют цикл, называется
круговой или циклической.
      Цикл длины 2 называется транспозицией (два элемента). Всякая
подстановка может быть представлена произведением транспозиций:

æ1 2 3 4 5ö æ1            2 3 4 5ö æ2        1 3 4 5ö
çç         ÷÷ = çç                 ÷×ç                ÷×
 è2 5 4 1 3ø è2           1 3 4 5 ÷ø çè 2    5 3 4 1 ÷ø
                  æ2      5 3 4 1ö æ 2       5 4 3 1ö
               × çç                ÷×ç                ÷ = (1, 2) × (1, 5) × (3, 4) × (1, 3)
                  è2      5 4 3 1 ÷ø çè 2    5 4 1 3 ÷ø

8

Страницы