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

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

Перестановки элементов записывают и в матричной форме где верхняя строка — это порядковые номера позиций элементов в перестановке; нижняя строка — тот же набор чисел взятых в каком-либо порядке; номер элемента на месте перестановки. Порядок столбцов в перестановках, записанных в матричной форме, не является существенным, так как в этом случае номер позиции каждого элемента в перестановке указывается явно в верхней строке. Например, перестановка (3,2,4,1) из четырех элементов может быть записана как

Задача оладьях. Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они «не били» друг друга?

Решение. Условие «не могли бить» означает, что на каждой горизонтали и вертикали может стоять лишь одна ладья. Ввиду этого, каждому расположению ладей на доске соответствует перестановка Верхняя строка перестановки — это номера горизонталей, нижняя — вертикалей, пересечение которых определяет положение ладей на доске. Следовательно, число расстановок равно числу перестановок из 8 элементов.