Число инверсий в подстановке

Число инверсий в подстановке

Вычисление определителей 4-го и более высоких порядков не может быть представлено достаточно простой «геометрической схемой», как это сделано для определителей 2-го и 3-го порядков.

Для определения и изучения определителей n-го порядка используются понятия, относящиеся к конечным множествам некоторых элементов.

Рассмотрим множество М целых чисел: 1, 2, … , n. Элементы множества М можно расположить разными способами.

Определение: всякое расположение чисел 1, 2, … , n в некотором порядке называется пе-рестановкой из n чисел. Общий вид записи перестановки из n элементов:

где каждое is есть одно из чисел 1, 2, … , n, причем ни одно из этих чисел не встречается дважды и не пропущено.

В качестве i1 можно выбрать любое из чисел 1, 2, … , n. Это дает n различных возможностей. Если i1 уже выбрано, то в качестве i2 можно выбрать лишь одно из оставшихся (n-1) чисел, т.е. различных способов выбрать числа (символы) i1 и i2 равно произведению n(n-1) и т.д. Число перестановок из n символов равно произведению:

Если в некоторой перестановке поменяем местами какие-либо два символа (не обязательно стоящие рядом), а все остальные оставим на месте, то получим новую перестановку. Такое преобразование перестановки называется транспозицией.

Теорема 1. Все перестановки из n символов можно расположить в таком порядке, что каждая следующая перестановка получается из предыдущей одной транспозицией, причем начинать можно с любой перестановки.

► При n=2 утверждение справедливо: 1, 2 → 2, 1;

Рассмотрим все перестановки из n элементов, у которых на первом месте стоит символ i1. Таких перестановок и их можно упорядочить в соответствии с требованиями теоремы для (n-1) символов. Пусть последняя из таких перестановок (с учетом того, что символ i1 был все время неперемещаем) имеет вид:

В перестановке (43), содержащей n символов, совершим транспозицию символа i1 с любым другим (например, с символом i2) и вновь упорядочим все перестановки из (n-1) символов при фиксированном на первом месте i2 и т.д. Так можно перебрать все перестановки из n символов. ◄

Следствие: от любой перестановки из n символов можно перейти к любой другой перестановке из тех же символов при помощи нескольких транспозицией.

Читайте также:  Виндовс 10 нечеткое изображение

Если в перестановке символ i1 стоит раньше, чем символ i2, но , то говорят, символы i1 и i2 составляют инверсию (нарушение порядка), иначе указанные символы составляют порядок. Перестановка называется четной, если ее символы составляют четное число инверсий, и нечетной – в противном случае.

Замечание: 1) всякая транспозиция меняет четность перестановки.

2) сумма порядков и инверсий постоянна и равна

Пример 31. Определим четность перестановки 1, 2, … , n.

Решение: Заданная перестановка четная, т.к. в ней нет инверсий (нарушений порядка).

Пример 32. Определите четность перестановки 4 5 1 3 6 2.

Решение: Для подсчета числа инверсий воспользуемся таблицей 1, в которой указаны инверсии выделяемых элементов со всеми последующими (учет нарушений порядка).

Дата добавления: 2015-07-23 ; просмотров: 6890 ; Нарушение авторских прав

Числа i и j образуют в перестановке инверсию, если i > j, но i расположено раньше j. Если число инверсий в перестановке четно, то перестановка называется четной, в противном случае нечетной. Например, перестановка (4 7 1 5 3 6 2) четна, так как число инверсий в ней 12 четно. Для определения числа инверсий в перестановке следует выбрать порядок их подсчета. Проще всего подсчитывать сколько инверсий образует число с последующими числами перестановки:

Inv(4 7 1 5 3 6 2) = 3 + 5 + 0 + 2 + 1+ 1+ 0 = 12.

Операция транспозиции заключается в перемене местами двух элементов перестановки.

Теорема. Одна транспозиция меняет четность перестановки на противоположную.

Доказательство. Теорема очевидна, если операции транспозиция подвергнуты два соседних числа перестановки. Пусть теперь между числами i и j находится s чисел. Для того, чтобы число j оказалось на месте i, его следует поменять местами с соседними s+1раз. А чтобы затем число i заняло место числа j его следует поменять местами с соседними s раз. Всего необходимо произвести операцию транспозиция над соседними числами s+1+s=2s+1нечетное число раз. Следовательно, четность перестановки изменится на противоположную. ■

Взаимно однозначное отображение множества из n элементов на себя называется подстановкой n-й степени. Подстановки принято записывать в следующем виде

Здесь мы работаем, как это часто делается в комбинаторике, не с самими элементами какого-либо множества, а с их номерами. В верхней строчке-числителе расположены элементы множества, а в нижней строчке-знаменателе расположены те элементы, в которые переходят соответствующие элементы числителя при отображении f,т.е. Конечно, элементы числителя могут быть расположены в ином порядке, чем естественный. Здесь подстановка записана в каноническом виде, когда порядок номеров в числителе естественный. И в числителе и в знаменателе подстановки стоят перестановки n-й степени. Если сумма инверсий в числителе и знаменателе четна, то подстановка называется четной, в противном случае нечетной. При любой замене местами столбцов подстановки ее четность не меняется. Для канонической записи подстановки

Читайте также:  Передача видео с телефона на телевизор samsung

Множество всех подстановок n-й степени обозначается через . Число всех подстановок n-йстепени равно n!. Введем на множестве S операцию умножения – композицию отображений. Пример умножения подстановок:

Теорема. Множество всех подстановок n-й степени образует группу относительно операции композиции отображений.

Для доказательства необходимо проверить выполнение всех аксиом группы. ■

Нейтральным элементом является тождественное отображение

Обратным элементом для подстановки является подстановка

Перестановка π множества X может быть записана в виде подстановки, например:

где и π(xi) = yi.

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

Случайная перестановка

Случайной перестановкой называется называется случайный вектор ξ = (ξ1. ξn), все элементы которого принимают натуральные значения от 1 до n, и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка ξ , для которой для некоторых pij, для которых и Если при этом pij не зависят от i , то перестановку ξ называют одинаково распределённой. Если же нет зависимости от j , то есть то ξ называют однородной.

См. также

  • Чётность перестановки (англ.)
  • Гигантская компонента

Wikimedia Foundation . 2010 .

Смотреть что такое "Инверсия (перестановка)" в других словарях:

Инверсия — В Викисловаре есть статья «инверсия» Инверсия: Инверсия в логике (от лат. inversio переворачивание, перестановка) переворачивани … Википедия

ИНВЕРСИЯ — (лат.). Превращение вообще и особенно превр. сахара в глюкозы и фруктозы. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. ИНВЕРСИЯ [лат. inversio переворачивание, перестановка] 1) лингв. изменение обычного порядка… … Словарь иностранных слов русского языка

ИНВЕРСИЯ — (от лат. inversio – перестановка) в психологии объемно наглядное переворачивание. Напр., когда наблюдатель движется вперед и назад на некотором расстоянии перед маской, расположенной на темном фоне и обращенной к наблюдателю внутренней стороной,… … Философская энциклопедия

Читайте также:  Умный фитнес трекер для android ios

ИНВЕРСИЯ НАСЕЛЁННОСТЕЙ — (от лат. inversio переворачивание, перестановка), неравновесное состояние в ва, при к ром для составляющих его ч ц (атомов, молекул и т. п.) выполняется неравенство: N2/g2>N1/g1, где N2 и N1 населённости верх. и ниж. уровней энергии, g2 и g1 их… … Физическая энциклопедия

Инверсия — нарушение принятого в разговорной речи порядка слов и, тем самым, обычной интонации; последняя при И. характеризуется большим, чем обычно, числом пауз. При И. 1. слова меняются местами («Швейцара мимо он стрелой» Пушкин; «Или души задушены… … Литературная энциклопедия

ИНВЕРСИЯ — (лат. inversio переворачивание, перестановка) в психологии процесс и результат нарушения нормального порядка и последовательности элементов, их перестановка или замена вплоть до противоположных. Феномен И. распространяется на мотивы, установки,… … Новейший философский словарь

перестановка — изменение, переключение, коммутация, транспозиция, перемещение, перегруппировка, коммутирование; передвижение, перекомпоновка, передислокация, метатеза, гипертеза, смешивание, движение, анаграмма, перетаскивание Словарь русских синонимов.… … Словарь синонимов

ИНВЕРСИЯ НАСЕЛЁННОСТЕЙ — (от латинского inversio переворачивание, перестановка), неравновесное состояние вещества, при котором в отличие от обычного состояния теплового равновесия количество составляющих вещество частиц (атомов, молекул), находящихся на более высоких… … Современная энциклопедия

инверсия — обращение, инвертирование, изменение Словарь русских синонимов. инверсия сущ., кол во синонимов: 7 • гомосексуализм (23) • … Словарь синонимов

Инверсия населённостей — (от латинского inversio переворачивание, перестановка), неравновесное состояние вещества, при котором в отличие от обычного состояния теплового равновесия количество составляющих вещество частиц (атомов, молекул), находящихся на более высоких… … Иллюстрированный энциклопедический словарь

Ссылка на основную публикацию
Чем отредактировать pdf файл бесплатно
Онлайн PDF редактор для изменения PDF Защищенная с помощью SSL передача файлов Автоматическое удаление файла с сервера через один час...
Функции в вольфрам математика
Функции пользователя Хотя в систему входят многие сотни встроенных функций (начиная от элементарных и кончая специальными математическими функциями и системными...
Функция abs в паскале
Возвращает абсолютную величину параметра. Объявление Function Abs(X) : (тип параметра); Режим Windows, Real, Protected Замечания Параметр X — выражение вещественного...
Чем очистить клей от корпуса телефона
На сенсорном дисплее телефона после снятия защитной пленки остались большие следы клея. Я понимаю, что не надо было экономить на...
Adblock detector