Тема 5.3 Подстановки. Обратные подстановки. Формула количества подстановок.

Взаимооднозначное отображение множества {1,2,3, …,n} на само себя называется подстановкой n чисел, где n – степень подстановки.

Обычно подстановку записывают в виде двух строк, заключенных в скобки. При этом в первой строке аргументы (первые координаты), а во второй строке в соответствующие им образы (вторые координаты).

Общая формула количества подстановок:

Если степень подстановки =n – то количество подстановок: n!

Из всех подстановок выделяют так называемую тождественную подстановку.

 

Если подстановка имеет вид , то симметричная ей подстановка получается если поменять местами строки подстановки

Произведением подстановок и называется новая подстановка , полученная путем применения сначала подстановки , затем подстановки .

Свойства:

1. - произведение подстановок не коммутативно;

2.

3.

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

Два числа образуют инверсию, если меньшее из них находиться правее большего.

Общее число инверсий определяют следующим образом:

1. определяем число инверсий для первой строки: для каждого числа подсчитываем количество чисел, меньше чем оно и стоящих правее его.

2. определяем число инверсий для второй строки: для каждого числа подсчитываем количество чисел, меньше чем оно и стоящих правее его.

3. складываем полученные значения.

1.

2.

3. 9 – нечетное, следовательно – нечетная подстановка.

Циклом называется такая подстановка, каждый элемент переходит в элемент , переходит в элемент , …, переходит в элемент , переходит в элемент

Цикл длины два называется транспозицией.

Любую подстановку можно представить в виде произведения независимых циклов.

Цикл длины один разрешается опускать в разложении подстановки в виде произведений.

Обозначим m – число независимых циклов: m=3.

Декрементом (d) называется разность n – m, где n – степень подстановки, m – количество независимых циклов. Четность подстановки совпадает с четностью ее декремента:

- нечетная подстановка.

Методика решения уравнений с подстановками:

1. , где - известные подстановки, х – неизвестная подстановка.

2. , где - известные подстановки, х – неизвестная подстановка

3.

Самостоятельная работа №12.

 

Контрольная работа

1 Вариант

 

1. Задано отображение f: .

Определить является ли заданное отображение сюръктивным, инъективным и взаимно однозначным, если

f(2)=2

f(3)=4

f(4)=5

f(5)=6.

2. Даны подстановки и .

Определить:

а) степень подстановок А, В.

б) обратные подстановки для А и В.

в) произведение подстановок .

3. Разложить подстановку в произведение попарно независимых циклов.

4. Определить чётность подстановки по декременту и по общему числу инверсий.

5. решить уравнение , если , , .

 

 

2 Вариант

 

1. Задано отображение f: .

Определить является ли заданное отображение сюръктивным, инъективным и взаимно однозначным, если

f(2)=3

f(3)=2

f(4)=4

f(5)=6.

f(6)=5.

2. Даны подстановки и .

Определить:

а) степень подстановок А, В.

б) обратные подстановки для А и В.

в) произведение подстановок .

3. Разложить подстановку в произведение попарно независимых циклов.

4. Определить чётность подстановки по декременту и по общему числу инверсий.

5. решить уравнение , если , , .

 

 

3 Вариант

 

1. Задано отображение f: .

Определить является ли заданное отображение сюръктивным, инъективным и взаимно однозначным, если

f(1)=4

f(2)=3

f(3)=2

f(4)=1

f(5)=4.

2. Даны подстановки и .

Определить:

а) степень подстановок А, В.

б) обратные подстановки для А и В.

в) произведение подстановок .

3. Для подстановки (1372)(45), заданной разложением в независимые циклы, найдите запись в обычной двух строчной форме, при условии, что степень подстановки равна 7.

4. Определить чётность подстановки по декременту и по общему числу инверсий.

5. решить уравнение ,

если , , .

 

4 Вариант

 

1. Задано отображение f: .

Определить является ли заданное отображение сюръктивным, инъективным и взаимно однозначным, если

f(8)=10

f(9)=15

f(5)=12

2. Даны подстановки и .

Определить:

а) степень подстановок А, В.

б) обратные подстановки для А и В.

в) произведение подстановок .

3. Для подстановки (13)(254), заданной разложением в независимые циклы, найдите запись в обычной двух строчной форме, при условии, что степень подстановки равна 5.

4. Определить чётность подстановки по декременту и по общему числу инверсий.

5. решить уравнение ,

если , , .

 

 

5 Вариант

 

1. Задано отображение f: .

Определить является ли заданное отображение взаимно однозначным, если

f(2)=2

f(3)=4

f(4)=5

f(5)=6

f(1)=3

f(6)=5.

2. Даны подстановки и .

Определить:

а) степень подстановок А, В.

б) обратные подстановки для А и В.

в) произведение подстановок .

3. Разложить подстановку впроизведение попарно независимых циклов.

4. Определить чётность подстановки по декременту и по общему числу инверсий.

5. решить уравнение ,

если , , .