Вычисление определителей 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 символов можно перейти к любой другой перестановке из тех же символов при помощи нескольких транспозицией.
Если в перестановке символ 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-й степени. Если сумма инверсий в числителе и знаменателе четна, то подстановка называется четной, в противном случае нечетной. При любой замене местами столбцов подстановки ее четность не меняется. Для канонической записи подстановки
Множество всех подстановок 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 – перестановка) в психологии объемно наглядное переворачивание. Напр., когда наблюдатель движется вперед и назад на некотором расстоянии перед маской, расположенной на темном фоне и обращенной к наблюдателю внутренней стороной,… … Философская энциклопедия
ИНВЕРСИЯ НАСЕЛЁННОСТЕЙ — (от лат. inversio переворачивание, перестановка), неравновесное состояние в ва, при к ром для составляющих его ч ц (атомов, молекул и т. п.) выполняется неравенство: N2/g2>N1/g1, где N2 и N1 населённости верх. и ниж. уровней энергии, g2 и g1 их… … Физическая энциклопедия
Инверсия — нарушение принятого в разговорной речи порядка слов и, тем самым, обычной интонации; последняя при И. характеризуется большим, чем обычно, числом пауз. При И. 1. слова меняются местами («Швейцара мимо он стрелой» Пушкин; «Или души задушены… … Литературная энциклопедия
ИНВЕРСИЯ — (лат. inversio переворачивание, перестановка) в психологии процесс и результат нарушения нормального порядка и последовательности элементов, их перестановка или замена вплоть до противоположных. Феномен И. распространяется на мотивы, установки,… … Новейший философский словарь
перестановка — изменение, переключение, коммутация, транспозиция, перемещение, перегруппировка, коммутирование; передвижение, перекомпоновка, передислокация, метатеза, гипертеза, смешивание, движение, анаграмма, перетаскивание Словарь русских синонимов.… … Словарь синонимов
ИНВЕРСИЯ НАСЕЛЁННОСТЕЙ — (от латинского inversio переворачивание, перестановка), неравновесное состояние вещества, при котором в отличие от обычного состояния теплового равновесия количество составляющих вещество частиц (атомов, молекул), находящихся на более высоких… … Современная энциклопедия
инверсия — обращение, инвертирование, изменение Словарь русских синонимов. инверсия сущ., кол во синонимов: 7 • гомосексуализм (23) • … Словарь синонимов
Инверсия населённостей — (от латинского inversio переворачивание, перестановка), неравновесное состояние вещества, при котором в отличие от обычного состояния теплового равновесия количество составляющих вещество частиц (атомов, молекул), находящихся на более высоких… … Иллюстрированный энциклопедический словарь
