Понятие о подстановке и перестановке. Алгебра

Понятие о подстановке и перестановке. Алгебра

Определение 1. Перестановкой степени n называется любая упорядоченная запись натуральных чисел 1, 2, 3, . . . , n в строчку одно за другим.

Например, 2, 4, 3, 1, 5. Это перестановка пятой степени. Вообще можно говорить о перестановках не только чисел, но и объектов любой природы, но сейчас для нас наибольший интерес представляет перестановка натуральных чисел. В принципе можно каждому объекту присвоить свой номер, тогда любая перестановка объектов может быть заменена перестановкой чисел. Можно смотреть на перестановку элементов как на перестановку их номеров.

ТЕОРЕМА 1. Существует n! различных перестановок n-ой степени из n чисел.

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

Докажем эту теорему. Рассмотрим n различных чисел a₁,a₂,a₃, . . . ,a_n. На первое место перестановки существует n способов выбора записи чисел; на второе место остаётся уже (n-1) способ выбора чисел; на третье место останется (n-2) варианта выбора и т.д., а на последнее место остаётся один единственный вариант. Тогда можем записать, что число всех перестановок n-ой степени из n элементов равно: n·(n-1)·(n-2)· . . . ·2·1=n!. Символ n! читается ЭН- факториал. Таким образом, n! означает произведение всех натуральных чисел, не превосходящих данного числа. Теорема доказана.

Определение 2. Говорят, что в данной перестановке два числа образуют инверсию (беспорядок), если большее из чисел в данной перестановке стоит левее меньшего. В противном случае эти два числа образуют порядок.

Пример: Рассмотрим перестановку шестого порядка: 2, 5, 1, 4, 6, 3

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

1 – две инверсии, затем единицу вычеркнем из перестановки; теперь возьмём двойку и подсчитаем, сколько чисел стоит левее двойки; 2 – ноль инверсий; вычёркиваем двойку и принимаемся за тройку; левее тройки стоит три числа, то есть тройка даёт нам три инверсии; вычёркиваем тройку и считаем, сколько чисел будет левее четвёрки; четвёрка даёт одну инверсию, вычёркиваем четвёрку и считаем количество чисел левее пятёрки; пятёрка даёт 0 инверсий, вычёркиваем пятёрку и считаем количество инверсий, которые даёт шестёрка; шестёрка даёт 0 инверсий.

1 – две инверсии; 2 – ноль инверсий; 3 – три инверсии; 4 – одна инверсия; 5 – ноль инверсий; 6 – ноль инверсий.

Общее число инверсий ,таким образом получается шесть.

Определение 3. Перестановка называется чётной, если общее количество инверсий есть чётное число и, соответственно, нечётной, если общее количество инверсий, содержащихся в этой перестановке , число нечётное.

Определение 4. Транспозицией называется такое преобразование перестановки, при котором какие – либо два её элемента меняются местами, а все остальные элементы остаются на своих местах.

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

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

Теорема 3. Любая транспозиция меняет чётность перестановки на противоположную.

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

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

Здесь и в той и в другой подстановке 1 переходит в 5; 2 переходит в 4; 3 переходит в 2; 4 переходит в 3 и 5 переходит в 1. Поэтому эти подстановки тождественные. Каждую подстановку можно записывать так, чтобы все числа в первой строке располагались в порядке возрастания. При такой записи подстановок любые две подстановки одной степени будут отличаться только перестановками во второй строке. Отсюда следует довольно простой и важный вывод: существует n! различных подстановок n – ой степени.

Определение 6. Будем называть подстановку чётной, если общее количество инверсий, содержащихся и впервой и во второй строчках чётное число и нечётной, если общее число инверсий в двух строчках – число нечётное.