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

При составлении размещений без повторений из п по k мы по­лучали расстановки, отличающиеся друг от друга либо составом, либо порядком элементов. Но если брать расстановки, которые включают все п элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называются перестановками из п элементов, а их число обознача­ется Р_n Следовательно, число перестановок равно Р_п ==п!. Перестановки элементов 1,2,..., п записывают и в матричной форме , где верхняя строка - это по­рядковые номера 1, 2,..., п позиций элементов в перестановке; нижняя строка - тот же набор чисел 1, 2,..., п, взятых в каком-ли­бо порядке; - номер элемента на j-м месте перестановки. По­рядок столбцов в перестановках, записанных в матричной форме, не является существенным, так как в этом случае номер позиции каждого элемента в перестановке указывается явно в верхней строке. Например, перестановка (3,2,4,1) из четырех элементов может быть записана как , , и т.д.

Пример:

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

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