АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Группа перестановок. Знак перестановки

Читайте также:
  1. B. группа: веществ с общими токсическими и физико-химическими свойствами.
  2. I. Обвально-осыпная группа склонов.
  3. II группа
  4. III. Задания для работы в малых группах.
  5. VIII. Подгруппа кислорода
  6. Административная группа
  7. АПРЕЛЬ (средняя группа)
  8. Беседа двадцать седьмая. Художественно-постановочная группа
  9. Вопрос №1 Общая и повозрастная смертность населения: методика расчета показателей, причины смерти в различных возрастных группах.
  10. Вывод: ведущим фактором является «Группа сверстников», то есть общение со своими сверстниками.
  11. Глава 2. Группа поддержки.
  12. Глебовская Анна, 2-ая французская группа

Напомним, что если – множество из -элементов, , то перестановкой степени называется взаимнооднозначное отображение . – множество всех перестановок степени : .

Лемма 1: Число различных перестановок равно

 

Лемма 2: Множество перестановок образует группу относительно умножения, так что , обратный элемент получается сменой строк (Не коммутативная группа).

Отметим, что если в перестановке поменять местами любые столбцы, то получится та же перестановка.

Углубим проведенное ранее исследование:

 

Определение 1: Пусть – перестановка степени , пусть . Тогда пара называется инверсией для , если .

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

Знак перестановки – это ,где – число инверсий.

Обозначается .

Итак, если – четная, то , и если – нечетная, то .

 

Пример: . Пары . Их них подчеркнутые – инверсии. Таким образом, , т.е. – четная.

 

Теорема 1:

1. Знак единичной перестановки равен 1.

2. Если .

3. .

Доказательство: 1. В единичной перестановке инверсий нет .

2. Пусть – множество инверсий относительно , а – множество инверсий относительно .

Легко видеть, что если , то . Следовательно, между множествами устанавливается взаимнооднозначное соответствие

.

  1. Пусть – множество инверсий относительно ,

– множество инверсий относительно ,

– множество инверсий относительно : .

Тогда надо доказать, что , т.е. четное число – это надо доказать.

Пусть ,

,

,

.

Введем следующее обозначение: пусть - это множество пар . Тогда справедлива следующая множественная схема:

 

Между множествами существует взаимнооднозначное соответствие : .

Поэтому из картинки видно , т.е. четное число. ▄

Следствие: .

Обозначение: Пусть . -перестановкой будем называть перестановку, при которой

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

 

Теорема 2: Транспозиция – нечетная перестановка.

Доказательство: Вычислим число инверсий. Инверсиями являются пары , где , пара , где , и пара . Их всего будет , т.е. нечетное число. ▄

Замечание: Произведение вида означает, что в нижней строке надо поменять местами и .

? Что означает .

Пример .

 

Теорема 3: Каждая перестановка является произведением конечного числа транспозиций.

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

Пример:

т.е. .

Аналогично в общем случае.

Пусть на втором шаге поменяются местами . Тогда ввиду замечания .

 

Упражнение: Каждая перестановка является произведением конечного числа транспозиций вида .

.

 

Теорема 4: При всех разложениях перестановки в произведения транспозиций, четность числа транспозиций одна и та же; она совпадает с четностью перестановки.

Доказательство: Пусть , где – транспозиция. Тогда знак равен знаку произведения транспозиций – четно, если – четно.


1 | 2 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)