Вопрос 8.

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

Пусть задано конечное множество элементов, которые можно занумеровать числами. М = {1, 2, 3…n} кроме расположения элементов в естественном порядке, данное множество можно упорядочить различными способами.

М = (1,2,3,4)(2,1,3,4)(3,4,1,2) и тд.

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

Доказать: число различных перестановок из n символов равно. Рn=1*2*3…n=n! (факториал)

Доказательство: Общий вид перестановки из n символов в виде i1,i2…in и тд, где i3 – есть одно из чисел. В качестве 1ого элемента данной перестановки может быть выбран любой из символов.

Способы выбора: i1=nраз i2=(n-1)раз i1i2=n(n-1)раз … in-1=2раза in = 1 раз

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

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

Доказательство: методом математической индукции.

1.n=2 для перестановок второго порядка истинно (1,2) (2,1) 1 транспозиция 2 перестановки

Теорема для перестановок 2ого порядка верна (2,1) (1,2) также

2.(n-1) элемент для любых перестановок из (n-1) символа. Теорема верна

3. Докажем, что теорема верна для перестановки из n символов. i1i2i3…in (1) Рассмотрим все перестановки из n символов, из кот.на первом месте есть эл.i1. Таких перестановок (n-1)! Раз. Их можно упорядочить в соответствии с требованиями теоремы. При этом начинать можно с перестановки(1), т.к. это сводится к упорядочению всех перестановок из (n-1) символов, кот.по предположению индукции можно начинать с любой перестановки, в частности перестановка вида (i2i3…in). В последней из таких перестановок из n символов совершаем транспозицию символа i1 с любым другим символом // с i2 и начинаем вновь получать перестановки, располагать эл.в нужном порядке, где на 1ом месте эл.i2, продолжая далее, перебираем все перестановки из n символов.

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

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

Теорема1: всякая подстановка может быть записана в след.виде:

Более удобен частный случай записи подстановки

2.Подстановка nой степени, при кот.все символы остаются на месте, называется тождественной и имеет вид

Пусть подстановка в виде1,тогда числа, входящие в верхнюю и нижнюю строку могут тметьодинаковую противоп. Четность. Переход к другой записи в подстановке А можно осуществить путем последовательного выполнения нескольких транспозиций в верх.строке и соотв. Им транспозии в нижней.Совершая транспозицию в верхней строке,и соотв. В нижней мы одновременно имеем четность обеих перестановок, при этом сохраняется совпадание или противоп.этих четнотсей.Отсюда следует, что при всех записях подстановки А четности верх.и ниж. Строки либо совпадает либо противоположна. В первом случае подстановка четная, во втором нечетная. Тождественная-всегда четная. Если подстановка записана в виде2, то в верхней строке всегда четная перестановка. Таким образом, число подстановок n степени = числу нечетных перестановок и = числу ½ n!

Для подстановки можно определять понятие обратной подстановки.

Подстановка обратная к подстановке А, если А* =Е или *А=Е Если А записана в виде2, то обратная =