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

Выведем теперь формулу для числа перестановок из п элементов.

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

Pn = n(n-1)(n-2) ·…·3·2·1.

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

Pn

= 1·2·3·…·(

n

-2)(

n

-1)

n

.

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

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

=

n

!

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

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

Применение данной формулы иллюстрируется в пособии следующими примерами.

Пример 2.

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

Число способов равно числу перестановок из 8 элементов. По формуле числа перестановок находим, что Р8 = 8!= 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40320.

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

Пример 3.

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

Из цифр 0, 2, 4, 6 можно получить Р4 перестановок. Из этого числа надо исключить те перестановки, которые начинаются с 0, т.к. натуральное число не может начинаться с цифры 0. число таких перестановок равно Р3. значит, искомое число четырехзначных чисел (без повторения цифр), которые можно составить из цифр 0, 2, 4, 6, равно Р4 – Р3. Получаем, Р4 – Р3 = 4! – 3! = 24 – 6 = 18.

Пример 4.

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

Сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 9, а 6 книг это можно сделать Р6 способами. В каждой из полученных комбинаций можно выполнить Р4 перестановок учебников. Значит, искомое число способов расположения книг на полке равно произведению Р6·Р4 = 6! ·4! = 720·24 = 17280.

Упражнения

Сколькими способами 4 человека могут разместиться на четырехместной скамейке?

Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов он может выбрать?

Сколькими способами 9 человек могут встать в очередь в театральную кассу?

В автосервис одновременно приехали 3 машины для ремонта. Сколько существует способов выстроить их в очередь на обслуживание?

Сколько есть способов раздать спортивные номера с 1 по 5 пяти хоккеистам?

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

Ольга помнит, что телефон подруги оканчивается цифрами 5, 6, 7, но забыла в каком порядке эти цифры следуют. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге.

Сколько шестизначных чисел (без повторения цифр) можно составить из цифр:

а) 1, 2, 5, 6, 7, 8; б) 0, 2, 5, 6, 7, 8?

Сколько среди четырехзначных чисел (без повторения цифр), составленных из цифр 3, 5, 7, 9, таких, которые:

а) начинаются с цифры 3; б) кратны 15?

Найдите сумму цифр всех четырехзначных чисел, которые можно составить из цифр 1, 3, 5, 7 (без их повторения).

Сколько чисел (без повторения цифр) можно составить из цифр 1, 2, 3, 4, таких которые:

а) больше 3000; б) больше 2000?

Семь мальчиков, в число которых входят Олег и Игорь, становятся в ряд. Найдите число возможных комбинаций, если:

а) Олег должен находиться в конце ряда;

б) Олег должен находиться в начале ряда, а Игорь – в конце;

в) Олег и Игорь должны стоять рядом.

Решение. а) так как место Олега фиксировано, то число комбинаций зависит от расположения остальных шести мальчиков. Значит число комбинаций равно Р6=6!=1·2·3·4·5·6=720.

б) Так как места Олега и Игоря фиксированы, то число комбинаций зависит от расположения пяти остальных мальчиков, т.е. равно Р5=5!=1·2·3·4·5=120.

в) Будем рассматривать пару Олег-Игорь как один элемент. Расположение этой пары и пяти остальных мальчиков может быть выполнено Р6=6! способами. В каждой из этих комбинаций Олег и Игорь могут располагаться Р2=2! Способами. Значит искомое число способов расположения мальчиков равно Р6·Р2=6! ·2!=720·2=1440.

В расписании на понедельник шесть уроков: алгебра, геометрия, биология, история, физкультура, химия. Сколькими способами можно составить расписание на этот день так, чтобы два урока математики (алгебра и геометрия) стояли рядом?