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

из пэлементов - конечная последовательность длины п, все элементы к-рой различны, т. е. П.- это размещение без повторения из пэлементов по п. Число перестановок равно п! Обычно в качестве элементов П. берут элементы множества Zn={1, 2,..., п};взаимно однозначное отображение p множества Zn на себя определяет перестановку [img: http://localhost:8080/file/041708-172.jpg]. Отображение p наз. подстановкой Zn. Многие задачи, связанные с перечислением П., формулируются в терминах подстановок, как, напр., задачи о перечислении П. с различными ограничениями на позиции переставляемых элементов (см., напр., [1], [2]). Перестановка [img: http://localhost:8080/file/041708-173.jpg] может рассматриваться как упорядоченное множество, состоящее из пэлементов, если считать, что элемент p(i) предшествует элементу p(i+l), i=1, 2,..., п. Примеры. 1) Пара (p(i), p(j)} образует в [img: http://localhost:8080/file/041708-174.jpg] инверсию, если p(i)>p(j) при i<j. Если а r - число П. из пэлементов с r инверсиями, то [img: http://localhost:8080/file/041708-175.jpg] 2) Если bn - число таких перестановок [img: http://localhost:8080/file/041708-176.jpg] из n элементов, что p(i)>p(i-1) при i четном и p(i)<p(i - 1) при iнечетном, то [img: http://localhost:8080/file/041708-177.jpg] Иногда П. наз. отображения в себя конечного множества, т. е. подстановки.