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

Пусть А - некоторое конечное множество, состоящее из n различных элементов:

Будем образовывать из элементов множества А упорядоченные множества. В качестве первого упорядоченного множества возьмем множество, в котором элементы расположены в порядке возрастания их номеров:

.

Второе упорядоченное множество можно образовать, поменяв местами элементы a₁ и a₂ , а все остальные элементы первого множества оставив на своих местах:

.

Аналогичным способом из элементов множества А можно строить и другие упорядоченные множества.

Примеры перестановок:

1) распределение n различных должностей среди n человек;

2) расположение n различных предметов в одном ряду, состоящем из n мест.

Перестановками из n элементов называются всевозможные конечные упорядоченные множества, содержащие n различных элементов, которые можно получить из некоторого данного множества, состоящего из n элементов.

Число перестановок n различных элементов обозначают P_n (читается Р из n ).

Пример. Пусть дано множество чисел {3;5;7}.Найти число перестановок.

Решение.

Этому множеству соответствует 6 перестановок: 357; 375; 537; 573; 753; 735.

Отметим, что перестановки состоят из одних и тех же элементов, но отличаются между собой порядком.

Теорема. Число перестановок n различных элементов равно n!, т. е.

(5.1)

Для пустого множества принимается соглашение: пустое множество можно упорядочить только одним способом; поэтому считается, что 0!=1.

Доказательство. Чтобы вывести формулу числа перестановок, представим себе n ячеек, пронумерованных числами 1, 2,..., n. Все перестановки будем образовывать, располагая элементы A_n в этих ячейках. В первую ячейку можно занести любой из n элементов (иначе: первую ячейку можно заполнить n различными способами). Заполнив первую ячейку, можно n-1 способом заполнить вторую ячейку (иначе: при каждом способе заполнения первой ячейки находится n-1 способов заполнения второй ячейки). Таким образом, существует n(n-1) способов заполнения двух первых ячеек. При заполнении первых двух ячеек можно найти n-2 способов заполнения третьей ячейки, откуда получается, что три ячейки можно заполнить n(n-1)(n-2) способами. Продолжая этот процесс, получим, что число способов заполнения n ячеек равно . Отсюда ,

P_n = n·(n - 1)·(n - 2)·...321 (5.2)

Число n·(n-1)·(n-2)·...321, то есть произведение всех натуральных чисел от 1 до n, называется «n-факториал»и обозначается n!. Отсюда P_n =n!

Пример. .

По определению считается: 1!=1; 0!=1.

Пример. Слова «барк» и «краб» образованы в результате перестановки букв, составляющих слово «брак». Определить число всевозможных перестановок букв в слове «брак».

Решение.

Так как исходное слово содержит 4 буквы, то число всевозможных перестановок вычисляется по формуле:

P₄ = 4! = 4 · 3 · 2 · 1 =24.