Спирина, М.С. Дискретная математика

Прикладной характер комбинаторики проявляется в ее приме­ нении в операционных исследованиях, в статистике и др. В оп е ­ рационных исследованиях она применяется для составления рас­ писаний, определения последовательности промышленных оп е ­ раций, распределения материала, маршрутов транспортных средств и т.д. 1.8. Подстановки Формулы —не душа математики. Но все-таки язык! Родной язык! Ю. В. Пухначев, Ю. П. Попов Рассмотрим множество Е„ = {1, 2, ..., л}, Упе N, каждый эл е ­ мент в котором представлен только один раз. Тогда взаимно-од­ нозначное отображение о„: Е„ -> Еп множества Еп на себя назы ­ вается подстановкой степени л. Множество подстановок л-й степени обозначается S„. Отношение Е„ -» Е„ бинарное, поэтому подстановки принято записывать в виде двухрядной матрицы, в первой строке которой записаны прообразы, а во второй — их образы: а = *i а(х,) *2 а(х2) Xi о(х,) j o (X j ) Ф . ) / / y < Л, X, Ф Xj. Если прообразы (аргументы) расположены в порядке возрас­ тания (при i <j , х, <Xj), запись подстановки такого вида называют канонической. Если аргументы не записаны в порядке возраста­ ния, то, переставляя столбцы (при этом сама подстановка не м е ­ няется, а изменяется лишь порядок произношения соответствий), можно верхнюю строку привести к упорядоченному виду: а = 1 2 ... х, о(1) о(2) ... о(х,) или (о,, о2, . . . , о„). По возможности будем пользоваться именно канонической записью. Напомним, что такая запись встречалась, когда мы з а ­ писывали перестановку из л элементов. Отметим, что прообразом перестановки служит произвольное конечное множество, а про ­ образом подстановки — обязательно Е„. Найдем число возможных различных подстановок степени п. Поскольку каждой канонической записи подстановки эквивалент­ на соответствующая перестановка, то число подстановок л-й сте­ пени равно числу перестановок из л элементов, т. е. множество S„ состоит из Рп= jiSj = л! элементов. 55