Задача 1. В финал вышли три бегуна. Сколькими способами они могут занять три призовых места? Обозначим бегунов 1, 2, 3 и запишем трёхзначным числом, кто какое место занял (231: первое место у бегуна 2, второе — у 3, третье — у 1). Все варианты: 123, 132, 213, 231, 312, 321 — их 6. Быстрее — по правилу произведения: первое место — любой из 3, второе — любой из 2 оставшихся, третье — последний: 3 · 2 · 1 = 6.
Задача 2. Сколько шестизначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6 без повторений? Выписывать их долго, а правило произведения даёт ответ сразу: 6 · 5 · 4 · 3 · 2 · 1 = 720.
В обеих задачах спрашивалось, сколькими способами можно расположить в разном порядке все элементы множества.
Определение. Упорядоченный набор всех элементов данного множества называют перестановкой. Число перестановок множества из n элементов обозначают P_n (от французского permutation — перестановка).
Теорема. P_n = n · (n - 1) · … · 2 · 1. Доказательство. Первый элемент можно выбрать n способами, при выбранном первом второй — (n - 1) способами и т. д.; для последнего остаётся один вариант. По правилу произведения получаем n · (n - 1) · … · 1.
Определение. Произведение первых n натуральных чисел называют факториалом числа n и обозначают n! (читают «эн факториал»): n! = 1 · 2 · 3 · … · n.
Формула числа перестановок: P_n = n!, n = 1, 2, 3, …
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| n! | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40 320 |
Факториал растёт очень быстро: 10! = 3 628 800, 20! — уже 19-значное число, а 50! — 65-значное.
Пример 1. Сколькими способами можно составить список 25 участников кружка (однофамильцев нет)? Это число перестановок 25 фамилий: P₂₅ = 25!. Число огромное, и ответ оставляют в виде 25!.
Пример 2. Сколько шестизначных чисел, делящихся на 5, можно составить из цифр 1, 2, 3, 4, 5, 6 без повторений? Число делится на 5, если оканчивается на 0 или 5; нуля нет, значит, последняя цифра — 5. Остальные пять цифр стоят перед ней в любом порядке: P₅ = 5! = 120 чисел.