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

При решении комбинаторных задач мы имеем дело с комбинациями из

некоторых предметов. Эти комбинации могут отличаться одна от другой чис

лом предметов, их составом или порядком.

Пример 4.1. В отделении сержанта Сбруева проходят службу 5 новобран

цев: Белкин, Пенкин, Фенькин, Свечкин и Овечкин. В свободное от нарядов

время сержант обучает их рассчитываться по порядку. По команде «В одну

шеренгу становись!» солдаты выстраиваются справа от Сбруева и по коман

де «По порядку номеров рассчитайсь!» производят расчёт: «первый—вто

рой—третий—четвёртый—пятый». После этого сержант перестраивает но

вобранцев по-новому, и расчёт повторяется. Сколько раз может Сбруев

повторить это упражнение, используя только разные способы построения

солдат?

Решение. Договоримся указывать порядок расположения солдат первыми

буквами их фамилий. Например, комбинация ПСОФБ означает, что первым

является Пенкин, вторым — Свечкин и т. д. Все комбинации отличаются од

на от другой порядком букв и называются перестановками из пяти букв.

Нам нужно найти число всех таких перестановок. Сначала мы выведем об

щую формулу, а потом закончим обсуждение примера.

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

соб нумерации этих элементов.

Напомним, что произведение 1·2·. . .·n = n! называется «эн факториал»

и по определению 0! = 1. Величина n! быстро растёт при увеличении n: 1! =

= 1, 2! = 1·2 = 2, 3! = 1·2·3 = 6, 4! = 1·2·3·4 = 24, 5! = 1·2·3·4·5 = 120,

6! = 720, 7! = 5040, 8! = 40320, 9! = 362880, 10! = 3628800.

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

равно n!.

Доказательство. Всякую перестановку из n элементов можно получить с

помощью следующих действий: первое действие — выбор первого элемента,

второе действие — выбор второго элемента, и т. д. Первый элемент можно

выбрать n различными способами; второй выбирается из оставшихся n − 1

элементов, поэтому число всех способов выполнения второго действия будет

n − 1. После выбора второго элемента их останется n − 2, следовательно,

число способов, которыми можно выполнить третье действие, будет n − 2.

Таким образом, число способов, которыми выполняется очередное дей

ствие, будет на единицу меньше предыдущего. Следовательно, четвёртое

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

действие можно выполнить (n − 3) способами, пятое — (n − 4) способа

ми и т. д., наконец, последнее действие — одним способом. По правилу

умножения число всех способов выполнения действий, то есть число всех

перестановок, равно n(n − 1) (n − 2) · . . . · 1 = n!. Теорема доказана.

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

мы доказали, что

Pn = n!. (4)

Возвращаясь к рассматриваемому примеру с новобранцами, где n = 5,

получим ответ P5 = 5! = 1 · 2 · 3 · 4 · 5 = 120.

Пример 4.2. В забеге участвуют 6 спортсменов. Найдите число возможных

исходов забега, если известно, что время у всех разное.

Решение. Каждый исход забега можно рассматривать как перестановку

из шести спортсменов в том порядке, в котором они прибежали к фини

шу. Поэтому число всех исходов равно числу всех перестановок из шести

элементов, P6 = 6! = 720.

Пример 4.3. На полку ставят шесть различных книг и журнал. Каково

число таких расстановок, при которых журнал находится посередине?

Решение. При каждом варианте расстановки книг три из них находятся

слева от журнала и три — справа от него. Один вариант отличается от

другого порядком расстановки книг. Поэтому каждый такой вариант можно

рассматривать как перестановку из шести книг. Следовательно, число всех

возможных вариантов будет P6 = 6! = 720.

Пример 4.4. Сколькими способами можно составить ведомость для на

числения зарплаты, если в список должны войти десять лиц?

Решение. Традиционный способ составления ведомости состоит в пере

числении лиц в алфавитном порядке. Отступив от него, мы получим другие

способы, каждый из них является некоторой перестановкой из десяти эле

ментов. Поэтому число всех способов составления ведомости равно числу

всех перестановок из десяти элементов, то есть P10 = 10! = 3628800.

Пример 4.5. В маршрутном такси 12 мест. Сколькими способами могут

занять их 12 пассажиров, среди которых 6 пенсионеров и для них отведены

первые места?

Решение. Представим себе посадку в такси в виде двух действий. Первое

действие: по своим местам рассаживаются 6 пенсионеров. Второе действие:

на свои места рассаживаются остальные 6 пассажиров. Число способов вы

полнения каждого из этих действий равно 6! = 720. По правилу умножения

число всех вариантов посадки будет 720 · 720 = 518400.

Упражнения

1. Выпишите все перестановки из букв a, b, c.

138 Глава V. Комбинаторные задачи

2. Сколько различных четырёхзначных чисел можно составить из цифр 7, 2, 4, 9, если каждая

цифра используется в записи числа только один раз?

3. С помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 закодируйте буквы А, В, Д, Е, Л, О, С, Т, Ь,

заменив каждую букву какой-нибудь цифрой, и зашифруйте слово СЛЕДОВАТЕЛЬ. Каково

число возможных вариантов кода?

4. Докажите равенство Pn = nPn−1 .

5. Докажите равенство n! = (n − k)! · (n − k + 1) · . . . · (n − 1) · n.