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

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

Рассмотрим пример. Пусть имеются три книги. Обозначим их буквами а, b и с. Эти книги можно расставить на полке по-разному.

Если первой поставить книгу а, то возможны такие расположения книг:

abc, асb.

Если первой поставить книгу b, то возможными являются такие расположения:

bас, bса.

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

cab, cba.

Каждое из этих расположений называют перестановкой из трех элементов.

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

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

В рассмотренном примере мы установили, что Р₃ = 6. Для того чтобы найти число перестановок из трех элементов, можно не выписывать эти перестановки, а воспользоваться комбинаторным правилом умножения. Будем рассуждать так. На первое место можно поставить любой из трех элементов. Для каждого выбора первого элемента есть две возможности выбора второго из оставшихся двух элементов. Наконец, для каждого выбора первых двух элементов остается единственная возможность выбора третьего элемента. Значит, число перестановок из трех элементов равно 3 • 2 • 1, т. е. 6.

Выведем теперь формулу числа перестановок из n элементов. Воспользуемся тем же способом рассуждений, который был использован для нахождения Р₃.

Пусть мы имеем л элементов. На первое место можно поставить любой из них. Для каждого выбора первого элемента на второе место можно поставить один из оставшихся n - 1 элементов. Для каждого выбора первых двух элементов на третье место можно поставить один из оставшихся n - 2 элементов и т. д. В результате получим, что

Р_n = n (n - 1) (n - 2) • ... • 3 • 2 • 1.

Расположив множители в порядке возрастания, получим

Р_n = 1 • 2 • 3 • ... • (n - 2)(n - 1)n.

Для произведения первых n натуральных чисел используют специальное обозначение: n! (читается «n факториал»).

Например, 2! = 1 • 2 = 2; 5!=1 • 2 • 3 • 4 • 5 = 120.

По определению считают, что 1! = 1.

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

Р_n = n!.

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

Число способов равно числу перестановок из 8 элементов. По формуле числа перестановок находим, что

Р₈ = 8! = 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 = 40 320.

Значит, существует 40 320 способов расстановки участниц забега на восьми беговых дорожках.

Пример 2. Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, б?

Из цифр 0, 2, 4, 6 можно получить Р₄ перестановок. Из них надо исключить те перестановки, которые начинаются с 0, так как натуральное число не может начинаться с цифры 0. Число таких перестановок равно Р₃. Значит, искомое число четырехзначных чисел равно Р₄ - Р₃.

Получаем

Р₄ - Р₃ = 4! - 3! = 24 - 6 = 18.

Пример 3. Имеется девять различных книг, четыре из которых — учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом?

Сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не девять, а шесть книг. Это можно сделать Р₆ способами. В каждой из полученных комбинаций можно выполнить Р₄ перестановок учебников. Значит, искомое число способов расположения книг на полке равно произведению Р₆ • Р₄.

Получаем

Р₆ • Р₄ = 6! • 4! = 720 • 24 = 17 280.

Продолжение >>>