Перестановки, декремент, циклы.

Задача 44. Дана подстановка . Определить её чётность с помощью декремента, с помощью подсчёта количества инверсий, с помощью матрицы.

Решение.   Разложим в произведение циклов.

, один цикл найден.

 второй цикл.

И так,  = (1245)(36).

, декремент чётный, значит, подстановка чётная.

Меньше и правее 2: 1       Меньше и правее 4: 1,3

Меньше и правее 6: 5,1,3 Меньше и правее 5: 1,3.

Здесь 8 инверсий, подстановка чётная.

Поиск инверсий при больших n  дольше, чем нахождение циклов. Нужно исследовать  пар. При  удобнее использовать чётность декремента, а не поиск всех инверсий. 

 

Построим матрицу подстановки, чтобы изучить ещё один способ поиска инверсий.

матрица:   

обозначим все пары, где 1 левее и ниже, это и есть те самые 8 инверсий: 

 

Задача 45. Дана матрица. Найти определитель, не вычисляя миноры.

Решение.   Здесь в каждой строке и в каждом столбце лишь по одной «1». Составим подстановку по этой матрице, найдём разложение на независимые циклы, и декремент.

= (146532) всего один цикл, , декремент нечётен, перестановка нечётна, тогда определитель матрицы равен . 

 

С помощью матрицы также могли найти и число инверсий: 

ПРАКТИКА 8. 06.03.2021

Разложение цикла в произведение транспозиций: 

=

Итого, (123) = (12)(13).

Задача 46. Дана подстановка на множестве из 8 элементов.

Найти число инверсий, чётность, порядок, декремент, матрицу подстановки. Найти разложение подстановки в произведение транспозиций.

 

Решение.  

Выбираем элементы, которые правее и меньше:

для 3:  1,2 для 4: 1,2 для 1: меньше не существует

для 8: 6,2,7,5 для 6: 2,5 для 2: нет для 7: 5  

для 5: правее ничего нет       Итого 11 инверсий. Нечётная. 

Разложим в произведение циклов.

(13)(24856)(7) 3 цикла, декремент , нечётный.

Порядок равен НОК (2,5,1) = 10. Цикл из 5 элементов перейдёт в тождественную подстановку через 5 шагов, но цикл (13) в это время (через нечётное число шагов) будет с инверсией, т.е. понадобится ещё 5 шагов, то есть 10 шагов .

Матрица подстановки. 

Разложение (13)(24856)(7)  в произведение транспозиций: 

(13) (24) (28) (25) (26) Проверка (какие 2 числа поменялись в этот момент, показано красным цветом): 

1 2 3 4 5 6 7 8

3 2 1 4 5 6 7 8

3 4 1 2 5 6 7 8

3 4 1 8 5 6 7 2

3 4 1 8 2 6 7 5

3 4 1 8 6 2 7 5

Если 2-й цикл записан начиная с 4: (13)(48562)(7)

Транспозиции: (13) (48) (45) (46) (42) (проверить самостоятельно).

 

Задача 47. Дана подстановка на множестве из 7 элементов.  

записать в виде произведения циклов, найти декремент и чётность. 

Решение.   

= (153)(247)(6) 

, декремент чётный, подстановка чётная.

Задача 48. Дана подстановка на множестве из 7 элементов.  

записать в виде произведения циклов, найти декремент и чётность. 

 

Решение.   

 = (1362) (47) (5) 

, декремент чётный, подстановка чётная.

Задача 49. Записать (136)(247)(5) в виде подстановки.

 

 

Решение, ответ.   

 

Задача 50. Записать (1572)(398)(46) в виде подстановки, определить чётность.

 

Решение, ответ.   

декремент , чётная. 

 

Задача 51. Умножить две подстановки, заданные в виде циклов.

(125)(346) и (1643)(25).

 

Решение.

 

Сначала запишем их в обычном виде.

(125)(346) =

(1643)(25) =

                    = (156)(2)(3)(4)  

Перерыв

Задача 52.

1) Сколько инверсий образует число 1, стоящее на k-м месте?

2) Сколько инверсий образует число n, стоящее на k-м месте?

1)

Правее и меньше – нет, так как 1 минимальное.

Левее и больше – все k-1 чисел, расположенные левее.

Ответ. k-1. 

2)

Левее и больше – не существует,

Правее и меньше -   n-k чисел.   

Ответ n-k.   

Задача 53. В какой подстановке из n чисел количество инверсий максимально, и чему оно равно? 

 

Каждый образует инверсию с каждым, если

Тогда 

 = . 

 

Глава 2. Числовые системы.