Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 содержание

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

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

Во-первых, подстановки удобнее записывать несколько в ином виде. Например, подстановку 1 ↔ 2, 2 ↔ 3, 3 ↔ 1 запишем в виде и обозначим ее какой-нибудь буквой, например, α. Читаем эту запись сверху вниз так: подстановка α переводит: 1 в 2, 2 в 3, 3 в 1.

Итак, эту подстановку можно кратко записать в следующей форме , которая по существу, означает запись перестановки В = (2, 3, 1) под перестановкой А = (1, 2, 3). Следовательно, для этого чтобы получить подстановку n элементов, мы должны взять две перестановки n элементов и отобразить их друг на друге взаимно однозначно. При этом, верхняя строка будет состоять из прообразов, а нижняя строка – из их образов при данном отображении. Другими словами, каждый столбик подстановки представляет собой запись связи прообраза х с его образом у согласно заданному отображению.

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

Например, подстановки α = и β = – равны.

Пусть дано множество М длины n. Рассмотрим всевозможные подстановки этого множества. Запишем их так, чтобы верхняя строка (строка прообразов) представляла собой нормальную перестановку. Тогда все различные подстановки будут отличаться только нижней строчкой, которых должно быть n! (как различных перестановок n элементов). Отсюда следует

Теорема 3. Подстановок n элементов равно n!.

Например, для множества М = {1} подстановок будет 1! = 1, для множества М = {1, 2}подстановок будет 2! = 1·2 = 2, для множества М = {1, 2, 3} подстановок будет 3! = 1·2·3 = 6, для множества М = {1, 2, 3, 4} подстановок будет 4! = 1·2·3·4 = 24 и т.д.

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

Например, подстановка α = нечетная, т.к. верхняя строка четная (0 инверсий), а нижняя – нечетная (т.к. она получена из верхней строки путём одной транспозиции – перемены мест двух элементов).

Теорема 4. Если поменять местами два столбика в подстановке, то ее четность не изменится.

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

Запишем все подстановки n элементов так, чтобы верхняя строка была в них нормальной перестановкой. Тогда четность подстановок будет зависеть только от четности нижних строк, в которой ½ n! четных и ½ n! нечетных при n ≥ 2

Отсюда следует

Теорема 5. При n ≥ 2 половина подстановок n элементов четная, половина – нечетная.

Замечаем, что в дальнейшем множество подстановок n элементов мы будем обозначать символом S_n.