Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Доказательство. 1. В единичной перестановке инверсий нет; поэтому
|
|
1. В единичной перестановке инверсий нет; поэтому 
.
2. Пусть 
– множество инверсий относительно 
, а 
– множество инверсий относительно 
.
Легко видеть, что если 
, то 
. Следовательно, между множествами 
устанавливается взаимнооднозначное соответствие
.
3. Пусть – множество инверсий относительно 
,
– множество инверсий относительно 
,
– множество инверсий относительно 
: 
.
Тогда надо доказать, что 
, т.е. 
. Таким образом, надо показать, что |A|+|B|+|C| – четное число.
Пусть 
,
,
,
.
Введем следующее обозначение: пусть 
- это множество пар 
. Тогда справедлива следующая множественная схема:
Между множествами 
существует взаимнооднозначное соответствие 
: 
.
Поэтому из картинки видно 
, т.е. четное число. ▄
Следствие. 
.
3о. Транспозиция как пример нечетной перестановки. Разложение перестановки в произведение транспозиций.
Определение 4. Перестановку вида 
, где точками обозначены элементы, остающиеся на своих местах, называют транспозицией (или 
-перестановкой).
Теорема 2. Транспозиция является нечетной перестановкой.
Доказательство. Вычислим число инверсий. Инверсиями являются пары 
, где 
; пары 
, где ; и пара 
. Их всего будет 
, т.е. нечетное число. ▄
Замечание. Для вычисления произведения 
и транспозиции 
вида 
необходимо в нижней строке поменять местами 
и 
.
Упражнение. Как вычисляется произведение 
?
Замечание. 
, т.е. эти транспозиции совпадают.
Теорема 3. Каждая перестановка является произведением конечного числа транспозиций.
Доказательство. Пусть 
. Покажем, что нижняя строка может быть получена из строки 
за конечное число шагов, каждый из которых состоит в том, что два числа меняются местами.
Пример. 
т.е. 
.
Аналогично в общем случае.
Пусть на r -ом шаге поменяются местами 
. Тогда ввиду замечания 
. ▄
Упражнение. Показать, что каждая перестановка является произведением конечного числа транспозиций вида 
.
Очевидно, что любая перестановка может быть представлена в виде произведения транспозиций различными способами.
Date: 2015-09-02; view: 606; Нарушение авторских прав