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

Определение. Перестановкой из элементов называется их расположение в определенном порядке: .

Две перестановки считаются различными, если хотя бы один элемент занимает в них разные позиции.

Пример. Все перестановки из трех элементов — цифр 1, 2, 3:

(1, 2, 3); (1, 3, 2); (2, 1, 3); (2, 3, 1); (3, 1, 2); (3, 2, 1).

Число перестановок из элементов принято обозначать через . Последний пример показывает, что .

Теорема. Для числа перестановок справедлива формула:

. (1)

Доказательство. При построении перестановки из элементов первый член может быть выбран способами. Для выбора второго члена перестановки остается способов, поскольку один элемент уже использован. Для выбора третьего члена остается способов, и т.д. Для предпоследнего члена перестановки остается способа, и, наконец, для последнего — способ, поскольку остался только один неиспользованный элемент.

По принципу умножения общее число различных перестановок равно произведению: . ▄

Примеры. 1. Очередь у причала из четырех судов под грузовую обработку может быть сформирована способами.

2. Колода из карт может быть растасована способами.