Часто т встречаются отображения множеств в себя, т е. отображения вида. Такие отображения называют

Часто т встречаются отображения множеств в себя, т.е. отображения вида . Такие отображения называют преобразованиями множества . Биективные преобразования назовем подстановками множества . Преобразование , такое, что для любого , называется тождественным преобразованием множества . Таким образом, оставляет на месте каждый элемент из . Часто вместо пишут просто , если из контекста ясно, какое множество имеется в виду. ^ Перестановки и подстановки В дальнейшем нам понадобятся некоторые дополнительные сведения о подстановках конечных множеств. Пусть — конечное множество, состоящее из элементов. Эти элементы можно перенумеровать с помощью первых натуральных чисел. Так как природа элементов множества для нас не важна, то будем считать, что . Всякое преобразование множества будем записывать так: (1) Если - подстановка, т.е. биективное преобразование, то в строке , , ..., выписаны все числа 1, 2, ..., без повторений, только, может быть, в другом порядке. Строки такого вида называются перестановками из чисел. Таким образом, перестановка из чисел - это расположение чисел 1, 2,..., в некотором определенном порядке. Две перестановки из чисел различаются порядком элементов, но не элементами. Пример 1. 1, 2, 3, 4; 3, 1, 2, 4;4, 2, 1, 3 - различные перестановки из четырех чисел. Итак, если - подстановка множества , то нижняя строка (1) есть некоторая перестановке из чисел. Обратно, если , , …, - произвольная перестановка из чисел, то преобразование множества является, очевидно, подстановкой. При этом различным перестановкам соответствуют различные подстановки. Теорема 1. Количество различных перестановок из чисел равно . Доказательство проведем индукцией по . При утверждение теоремы очевидно. Будем считать, что и число различных перестановок из чисел равно Разобьем множество всех перестановок из чисел на классы, состоящие из перестановок с одинаковым последним числом. Таких классов будет ровно . Перестановок, лежащих в одном классе с перестановкой , , …, , будет столько, сколько существует различных перестановок из чисел , , …, , т.е. . Так что каждый класс содержит ровно перестановок. Но тогда число всех перестановок из чисел равно . Следствие 1. Число всех подстановок множества из элементов равно . Пример 2. Выпишем все перестановки из трех чисел: 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 1, 2; 3, 2, 1. Так как число различных перестановок из трех чисел равно , то других перестановок нет. Определение 1. Пусть , , …, (1) есть перестановка из чисел. Подмножество множества называется инверсией в перестановке (1), если большее из этих двух чисел стоит в перестановке (1) перед меньшим. Если же большее из чисел i, j стоит в (1) после меньшего, то подмножество {i, j} называется порядком в перестановке (1). Пример 3. В перестановке 3, 5, 4, 1, 2 {3, 4} - порядок, а {3, 1} - инверсия. Определение 2. Перестановка называется четной, если она содержит четное число инверсий. В противном случае перестановку называют нечетной. Пример 4. Определить характер четности перестановки 3, 5, 4, 1, 2. (2) Для этого выпишем все инверсии перестановки (2): {3, 1},{3, 2}, {5, 4}. {5, 1}, {5, 2}, {4, 1}, {4, 2}. Так как их оказалось семь, то (2) - нечетная перестановка. Пример 5. Перестановка 1, 2, …, n имеет 0 инверсий и поэтому является четной. Пусть , , …, (3) и , , …, (4) есть две перестановки из чисел, а - подстановка множества . Будем говорить, что подстановка переводит перестановку (3) в перестановку (4), если , . Таким образом, фраза «применить к перестановке (3) подстановку » будет означать «заменить перестановку (3) перестановкой ,, …, ». Особый интерес для нас будут представлять подстановки одного специального вида. Подстановка множества называется транспозицией, если для некоторой пары чисел , , , , а всякое другое число из оставляет на месте. Такую транспозицию удобно обозначать символом (не путайте с элементом множества ). Очевидно, - равенство отображений. Если транспозицию применить к перестановке ..., , ..., , ..., то, очевидно, получится перестановка ..., , ..., , ..., где многоточия указывают числа, остающиеся без изменения. Таким образом, после применения к перестановке транспозиции элементы меняются местами. Теорема 2. Если к перестановке один раз применить транспозицию, то характер четности ее изменится на противоположный. Рассмотрим сначала случай, когда транспозиция применяется к перестановке ..., , , ..., (5) в которой числа стоят рядом. В результате получается перестановка ..., , , ... (6) Число инверсий в перестановке (6) на единицу больше или меньше, чем в (5). Действительно, взаимное расположение чисел с остальными числами, входящими в перестановки (5), (6), не изменилось. В то же время, если - инверсия в (5), то - порядок в (6), если же - порядок в (5), то - инверсия в (6). Пусть теперь транспозиция применяется к перестановке ..., , , ..., , , ... (7) Эта транспозиция переводит (7) в перестановку ..., , , ..., , , ... (8) С другой стороны, перестановку (8) можно получить из перестановки (7), применяя последовательно транспозиции , , ..., , , , , ..., . Всего транспозиций. Так как на каждом шаге меняются местами соседние числа, то, согласно уже доказанному, всякий раз мы теряем или приобретаем точно одну инверсию, т. е. изменяем характер четности перестановки на противоположный. Теперь ясно, что характе­ры четности перестановок (7) и (8) различны. Следствие 2. Если , то количество всех четных перестановок из чисел равно количеству всех нечетных перестановок из чисел и, следовательно, равно . Обозначим буквой количество всех четных перестановок из чисел, а буквой - количество всех нечетных перестановок из чисел. К каждой из четных перестановок применим одну и ту же транспозицию. Все полученные в результате этого перестановки нечетны и различны, их число равно . Следовательно, . Аналогично доказывается, что . В результате и, так как различных перестановок из чисел ровно , получаем . Предложение 1. Пусть . От любой перестановки из чисел можно перейти к любой другой перестановке из чисел, последовательно применив несколько подходящих транспозиций. Пусть , , …, (9) и , , …, (10) есть произвольные перестановки из п чисел. Если , то, применив к перестановке (9) транспозицию , получим перестановку из п чисел вида , , …, . (11) Если , то применим к перестановке (11) транспозицию . В результате получим перестановку вида , , , …, . Продолжая этот процесс, получаем требуемое. Пример 6. Найти последовательность транспозиций, переводящую перестановку 1, 2, 3, 4 в перестановку 4, 1, 2, 3. Решение. Записываем , так что - искомая последовательность транспозиций. Вернемся к изучению подстановок конечного множества. Для любых двух подстановок и множества определено произведение , которое снова есть подстановка . Договоримся вместо писать в дальнейшем . Пример 7. Пусть , . Проверить, что . Решение. Действительно, ; ; . Так как всякая транспозиция множества есть подстановка этого множества, то транспозиции можно перемножать. При этом произведение транспозиций есть некоторая подстановка множества , но, как правило, не транспозиция. Пример 8. Если , то произведение не является транспозицией. Теорема 3. Всякую подстановку конечного множества , содержащего не менее двух элементов, можно представить в виде произведения транспозиций этого множества. Если - тождественная подстановка множества , то , где - любая транспозиция . Пусть есть произвольная нетождественная подстановка . Рассмотрим перестановки 1, 2, ..., (12) и , , …, . (13) Согласно предложению 3.3, существует последовательность транспозиций , переводящая перестановку (12) в перестановку (13). Это означает, что для любого , , …, . Но тогда т. е. . Пример 9. Представить подстановку в виде произведения транспозиций. Решение. Найдем последовательность транспозиций, переводящих перестановку 1, 2, 3, 4 в перестановку 4, 3, 1, 2: Следовательно, . Разложение подстановки в произведение транспозиций определено не однозначно. Так, например, к любому такому разложению всегда можно приписать произведение . Однако верна Теорема 4. Характер четности числа сомножителей в разложении подстановки в произведение транспозиций не зависит от выбора разложения. Пусть и произвольное разложение в произведение транспозиций. Покажем, что имеет тот же характер четности, что и перестановка , , …, . В самом деле, так как , то для любого , , …, . Это означает, что последовательность транспозиций переводит перестановку 1, 2, ..., в перестановку , , …, . Но перестановка 1, 2, ..., четная, а каждое применение транспозиции меняет характер четности перестановки. Поэтому число является четным тогда и только тогда, когда перестановка , , …, четная. Это доказывает теорему. Определение 3. Подстановка называется четной, если она разлагается в произведение четного числа транспозиций, и нечетной в противном случае. Из доказательства теоремы 3.7 следует Предложение 2. Подстановка является четной тогда и только тогда, когда , , …, - четная перестановка. Следовательно, количество четных подстановок из чисел равно . Предложение 3. Подстановки и имеют один характер четности. Достаточно проверить, что если - произведение транспозиций, то . В заключение сделаем одно полезное замечание. Подстановку иногда удобно записывать в виде (14) где , , …, - некоторая перестановка из чисел. Так, если , то . При необходимости всегда можно перейти от записи (14) к обычной записи. Пример 10.

Похожие:

	Базовой технологии создания систем обработки и отображения сложно организованной информации В нивц мгу разрабатывается инструментальный комплекс "виз" для создания систем обработки и отображения сложно		Технологии создания систем обработки и отображения сложно организованной информации В нивц мгу разрабатывается инструментальный комплекс "виз" для создания систем обработки и отображения сложно
	Вопросы для подготовки к экзамену за 2 семестр Отношения на множествах. Бинарные отношения, способы задания. Отображения множеств		Ю. А. Тяпченко анализ и синтез подсистемы аварийно-предупредительной... Гнализации систем отображения информации пилотируемых космических аппаратов / Тяпченко Ю. А.; Закрытое акционерное общество «Научно-технический...
	Ю. А. Тяпченко системы отображения информации космической станции... Системы отображения информации космической станции «мир» и транспортного корабля «союз»		Тесты к зачёту по дисциплине «искусство ХХ века» Что характерно для Авангардизма поиск новых, неизвестных, часто штучных форм и средств художественного отображения, недооценка или...
	Eco дигитайзер Имеется возможность использовать различные технологии ввода лекал, такие как: поворот, копирование или получение зеркального отображения....		Windows xp как сервер терминалов Мб озу (помните еще такие?) запускать, используя «удаленный рабочий стол», ms office 2003 (оно, собственно, и понятно, ресурсы локальной...
	Ч/Б простой компрессор с функцией отображения в реальном времени Необходимо избегать попадания воды или другой жидкости на данное оборудование. Не		«Анализ возможностей использования системы Microsoft Office Excel...