Лекция 14. Операции над подстановками
Подстановка на множестве M – это биекция [7]:
В случае конечного множества M (как выше) количество подстановок определяется как количество перестановок из n элементов:
Можно считать, n ящиков заполняются объектами x1, …, xn, xi Î M. Поскольку M биективно Nn, можно определить подстановку как Nn ® Nn, т.е. иметь дело только с натуральными числами:
{i1, i2, …, in} = Nn.
Обычно подстановка задается в форме стандартной таблицы, имеющей две строки. Верхняя строка всегда содержит последовательные натуральные числа, начиная с 1. В нижней строке, конечно, не должно быть повторений. Например:
Подстановка, как и любое бинарное отношение, может быть составной
Видно, что в «контрпримере» В составе любой подстановки можно выделить циклы. Их длина может составлять 1, 2, …, n. Цикл длины 1 – это фактически вырожденный цикл, стационарный элемент.
|
M ® Nn, n = |M| Î N.
.
, т.е. «произведение» подстановок некоммутативно.
