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

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

Первый элемент множества обозначим символом второй Булем иметь конечную последовательность которую называют перестановкой из элементов.

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

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

Так, из букв а и можно образовать перестановки: а из букв и с — шесть перестановок:

Число всевозможных перестановок из элементов обозначают символом

Теорема. Уасло различных перестановок из элементов равно произведению последовательных натуральных чисел от 1 до включительно, т. е.

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

Чтобы определить число перестановок из элементов подсчитаем сначала число перестановок из элементов, начинающихся каждым из этих элементов. Если перед каждой из перестановок из элементов мы поставим элемент а, то получим все различные перестановки из элементов начинающиеся элементом а; их будет Аналогичным способом находим, что каждое из чисел всех различных перестановок из элементов, начинающихся каждым из элементов равно

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

Так как, по предположению, то

следовательно, в силу принципа математической индукции теорема верна для всякого натурального числа

Пример. Сколько пятизначных чисел можно записать посредством цифр 1, 2. 3, 4, 5, если ни одна из цифр в записи числа не повторяется дважды

Искомое число равно числу всех возможных перестановок из пяти элементов, т. е.