Курсовая работа: Перестановки и подстановки, группа подстановок

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО

СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РЕСПУБЛИКИ УЗБЕКИСТАН

ФЕРГАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет

Математика-информатика

КУРСОВАЯ РАБОТА

на тему:

«Перестановки и подстановки, группа подстановок»

студента II курса 20.06 (р)(А) группы

направления «математики»

Юсуфжанов Маъруфа

Руководитель: доцент кафедры

Шерматов А.А

Фергана 2021

Содержание

Введение

ГЛАВА 1. Перестановки

1.1. Основные понятия и теоремы

1.2. Транспозиция перестановки

ГЛАВА 2. Глава 2. Подстановки и операции над ними

2.1 Подстановки

2.2 Циклические подстановки

2.3 Умножение подстановок

2.4 Разложение подстановок в произведение циклов с непересекающимися орбитами

Заключение

Использованные литературы

Введение

В комбинаторике перестаномвка -- это упорядоченный набор чисел  обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.

В теории групп под перестановкой (подстановкой) произвольного множества подразумевается биекция этого множества на себя.

Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки. Более существенное отличие состоит в том, что подстановка -- это непосредственно функция, а перестановка -- результат применения этой функции к элементам последовательности.)

Термин «перестановка» возник потому, что сначала брались объекты, каким-то образом расставленные, а другие способы упорядочения требовали переставить эти объекты.

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

В дальнейшем нам будут нужны некоторые свойства взаимно однозначных отображений конечного множества на себя. Такие отображения называются подстановками. Название объясняется такой интерпретацией отображения: каждый элемент остается на месте либо вместо него подставляется другой элемент того же множества. Множество всех подстановок «-элементного множества {а[,...,а_п} обозначается S_n = S_n(a,..., а_п).

Глава 1. Перестановки

1.1. Основные понятия и теоремы

Определение 1.1. Всякое расположение чисел 1, 2, ... , n в некотором определенном порядке называется перестановкой из n чисел. Другими словами, под перестановками чисел принято понимать всевозможные способы, которыми эти числа можно выстроить в ряд.

Можно подсчитать число таких способов. Одно число можно выстроить в ряд одним способом. Два числа - двумя способами: 1, 2 и 2, 1. Числа 1, 2, 3 можно выстроить в ряд следующими способами:

1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1.

Всего их шесть. Действительно, на первом месте могут стоять только числа 1, 2 и 3, а два остальных числа в каждом из трех возможных случаев можно выстроить в ряд двумя способами. Аналогичный принцип позволяет подсчитать число перестановок из четырех чисел: 1, 2, 3 и 4. Любое из чисел 1, 2, 3 и 4 может стоять на первом месте, а число всех перестановок трех остальных элементов есть 6:

Число перестановок из четырех элементов равно 4·6=24, т.е. умножаем число перестановок из трех элементов (всего их 6) на 4. Шесть перестановок из трех чисел мы получим, умножив число перестановок из двух чисел (всего их 2) на 3. Таким образом, число перестановок из четырех элементов можно представить в виде 24=4·3·2·1. Можно показать, что число перестановок из пяти чисел равно 5·4·3·2·1=120.

Теорема 1.1. Число различных перестановок из n чисел равно произведению 1·2·3· ...·n, обозначаемому n! (читается: "эн факториал").

Доказательство. Действительно, общий вид перестановки из n символов есть i₁, i₂, ... , i_n, где каждое из i_s есть одно из чисел 1, 2, ... , n, причем ни одно из этих чисел не встречается дважды. В качестве i₁ можно взять любое из чисел 1, 2, ... , n; это дает n различных возможностей. Если, однако, i₁ уже выбрано, то в качестве i₂ можно взять лишь одно из оставшихся n-1 чисел, т.е. число различных способов выбора пары символов i₁, i₂ равно произведению n(n-1). Если, уже выбраны i₁ и i₂, то в качестве i₃ можно взять лишь одно из оставшихся n-2 чисел, т.е. число различных способов выбора тройки символов i₁, i₂, i₃ равно произведению n(n-1)(n-2) и т.д. Аналогично, если выбраны числа i₁, i₂, i₃, ..., i_n-2, то в качестве i_n-1 можно взять лишь одно из оставшихся двух чисел, а возможность выбора для i_n остается одна. Таким образом, число различных способов, которыми можно выбрать символы i₁, i₂, … , i_n равно произведению n·(n-1)·(n-2)·(n-3)·...·2·1=1·2·3· ...·(n-2)·(n-1)·n=n! Теорема доказана.

Определение 1.2. Говорят, что в данной перестановке числа i и j составляют инверсию, если i>j, но i стоит в этой перестановке раньше j.

Определение 1.3. Перестановка называется четной, если ее числа составляют четное число инверсий, и нечетной - в противоположном случае.

Например, перестановка 4, 5, 1, 3, 6, 2 четная, так как число инверсий в ней равно 8. Перестановка 1, 2, ... , n будет четной при любом n, так как число инверсий в ней равно нулю.

1.2. Транспозиция перестановки

Определение 1.4. Преобразование в перестановке, при котором мы поменяем местами какие-либо два символа (необязательно стоящие рядом), а все остальные символы оставим на месте, называется транспозицией.

Всего n(n-1)!=n! перестановок. Этим путем можно перебрать все n! перестановок из n символов. Теорема доказана.

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

Теорема 1.1. Всякая транспозиция меняет четность перестановки.

Доказательство. Для доказательства этой теоремы рассмотрим сначала случай, когда транспонируемые символы i и j стоят рядом, то есть перестановка имеет вид

... , i, j, ... ,

где многоточия заменяют те символы, которые не затрагиваются транспозицией. Транспозиция превращает нашу перестановку в перестановку

..., j, i, ... , причем, понятно, в обеих перестановках каждый из символов i, j составляет одни и те же инверсии с символами, остающимися на месте. Если символы i и j раньше не составляли инверсии, то в новой перестановке появляется одна новая инверсия, т.е. число инверсий увеличивается на единицу. Если же i и j раньше составляли инверсию, то теперь она пропадает, т.е. число инверсий на единицу уменьшается. В обоих случаях четность перестановки меняется.

Пусть теперь между транспонируемыми символами i и j расположены s

(s>0) символов, т.е. перестановка имеет вид

... i, k₁, k₂, ... , k_s, j,...

Транспозицию символов i, j можно получить в результате последовательного выполнения 2s+1 транспозиций соседних элементов. А именно, это будут транспозиции, переставляющие символы i и k₁, затем i (уже стоящее на месте символа k₁) и k₂ и так далее, пока i не займет место символа k_s. За этими s транспозициями следует транспозиция, перемещающая символы i и j, а затем s транспозиций символа j со всеми k, после чего j занимает место символа i, а символы k возвращаются на свои старые места. Таким образом, мы нечетное число раз меняли четность перестановки, а поэтому перестановки

... , i, k₁, k₂, ... , k_s, j, ... и ..., j, k₁, k₂, ... , k_s, i, ... имеют противоположные четности. Теорема доказана.

Из теорем 1.2 и 1.3 вытекает, что при n ?2 число четных перестановок из n символов равно числу нечетных, то есть равно n! . Определим новое понятие, понятие подстановки n-й степени.

Глава 2. Подстановки и операции над ними

2.1 Подстановки

Определение 1. Произвольное взаимно однозначное отображение множества первых ?? натуральных чисел называется подстановкой m -го порядка.

Замечание 1. Часто подстановки называют перестановками.

Обычно подстановку  изображают следующим образом: , что задает образы всех элементов: ,  и так далее. Также используют запись .

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

Определение 2. Элемент  подстановки называется действительно перемещаемым, если .

Пример 2. В подстановке  два действительно перемещаемых символа: 1 и 3.

Операция умножения на подстановках определяется как композиция отображений, причем знак композиции  обычно опускают

.

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

При всех записях подстановки A четности верхней и нижней строк совпадают, либо же при всех записях они противоположны.

Определению четности подстановки можно дать другие формы.

Определение 1.6. Подстановка A будет четной, если общее число инверсий в двух строках четно, и нечетной в противном случае.

Предложение 1. Четность подстановки не зависит от способа разложения подстановки в произведение транспозиций.

Предложение 2. Для двух подстановок  и  четность их произведения равна произведению четностей:

.

Доказательство.

Предложение 3. Пусть  -- цикл длины . Тогда его четность равна .

Доказательство.

Определение 1.7. Пусть  -- разложение подстановки в произведение независимых циклов длин . Число  называется декрементом - подстановки .

Предложение 4. Пусть  -- разложение подстановки в произведение независимых циклов длин . Тогда четность подстановки  вычисляется по формуле

.

Доказательство.

Пример 1. Любая транспозиция -- это нечетная подстановка. Подстановка из примера 4 нечетная, так как декремент  -- нечетное число.

Пример 2. Любая подстановка, в разложении которой на независимые циклы все циклы имеют нечетные длины , четна, так как ее декремент -- это сумма  четных чисел .

Определение 1.7. Результат последовательного выполнения двух взаимно однозначных отображений множества 1, 2, ... , n на себя снова будет, некоторым взаимно однозначным отображением этого множества на себя, то есть подстановкой n-й степени, называемой произведением первой из заданных подстановок (первое отображение) на вторую.

Пример 1. Рассмотрим симметрическую группу третьей степени - группу всех взаимно однозначных отображений множества, состоящего из трех элементов а, b, с, -- например, это могут быть числа 1, 2, 3, на себя. Так как из трех элементов можно составить всего шесть различных перестановок:

то и число различных подстановок для них равно шести. Обозначать их удобно следующим образом:

где, например,  такое отображение множества 1, 2, 3 «а себя, при котором  (1 отображается в 2), и . Подстановки, отличающиеся только порядком следования столбцов, например,

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

ибо в правом множителе , в левом , следовательно, в произведении , и т.д. Единицей при этом умножении служит тождественная подстановка  и для каждой подстановки имеется обратная ей:

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

Группу  можно представить такой таблицей Кэли:

Группа  некоммутативна, так как, например,

(таблица Кэли этой группы не симметрична относительно главной диагонали).

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

показывающим, что 1 переходит в  здесь 2- в , и т.д.; здесь -- это те же числа 1,2,…,n но расположенные, вообще говоря, в каком-то другом порядке. Расположение столбцов в этой записи не играет роли и, например,

Число подстановок из n элементов равно, очевидно, n!.

Перемножаются подстановки в общем случае так же, как подстановки из трех элементов. Так, например,

(Сначала выполняется правая подстановка, а потом левая: здесь 1-4, а затем 4-1; далее, 2-3, а затем 3-4; и т. д.) Умножение подстановок ассоциативно, но, вообще говоря, не коммутативно. Подстановка