Размещения, перестановки, сочетания

§3. Размещения, перестановки, сочетания

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

Пример 1. Пять бойцов сержанта Сбруева.

В отделении сержанта Сбруева проходят службу 5 новобранцев: Белкин, Пенкин, Фенькин, Свечкин и Овечкин. В свободное от нарядов время сержант обучает их, как рассчитаться по порядку. По команде «В одну шеренгу становись!» солдаты выстраиваются справа от Сбруева и по команде «По порядку номеров рассчитайсь!» производят расчет: «первый-второй-третий-четвертый-пятый». После этого сержант перестраивает новобранцев по-новому и расчет повторяется. Сколько раз может Сбруев повторить это упражнение, используя только разные способы построения солдат?

Решение. Договоримся указывать порядок расположения солдат первыми буквами их фамилий. Например, комбинация ПСОФБ означает, что первым является Пенкин, вторым — Свечкин и т.д. Все комбинации отличаются одна от другой порядком букв и называются перестановками из пяти букв. Нам нужно найти число всех таких перестановок. Сначала мы выведем общую формулу, а потом закончим обсуждение примера.

Пусть дано множество из п элементов. Занумеруем все элементы каким-нибудь способом от 1 до п (в случае с новобранцами п = 5). Ясно, что занумеровать можно многими способами.

Определение. Перестановкой из п элементов называется всякий способ нумерации этих элементов.

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

Доказательство. Всякую перестановку из п элементов можно получить с помощью п действий: первое действие — выбор первого элемента, второе действие — выбор второго элемента, и т.д., наконец, n-е действие — выбор элемента с номером п.

Рекомендуемые материалы

Первый элемент можно выбрать п различными способами; второй выбирается из оставшихся п - 1 элементов, поэтому число всех способов выполнения второго действия будет п - 1. После выбора второго элемента их останется п - 2, следовательно, число способов, которыми можно выполнить третье действие, будет п - 2. Таким образом, число способов, которыми выполняется очередное действие, будет на единицу меньше предыдущего. Следовательно, четвертое действие можно выполнить (п - 2) способами, пятое — (п - 4) способами и т.д., наконец, последнее действие — одним способом.

По правилу умножения (теорема 1) число всех способов выполнения действий, т.е. число всех перестановок, равно п(п - 1)(п - 2) • ... • 1 = п!. Теорема доказана.

Число всех перестановок из п элементов обозначают Р_п. Согласно теореме 1 его можно найти по формуле

Р_п = п!.                                                                 (4)

Например, в случае с новобранцами (п = 5) мы получим Р₅ = 5! = 120.

УПРАЖНЕНИЯ

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

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

9. Проверьте равенство Р₆ = 6Р₅.

10. Что больше: Р₇ или 2⁷?

11. С помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 закодируйте буквы А, В, Д, Е, Л, О, С, Т, Ь, заменив каждую букву какой-нибудь цифрой, и зашифруйте слово СЛЕДОВАТЕЛЬ. Каково число возможных вариантов кода?

Пример 2. Однажды утром

Однажды утром по улицам города Дрюкова на высокой скорости пронеслась машина. Она сбила зазевавшегося поросенка и скрылась в неизвестном направлении. Возвращавшийся из ресторана житель N, заметил номер автомобиля. Но когда появилась милиция, он с перепугу вспомнил только, что номер четырехзначный, все цифры разные, причем первая цифра 1, а последняя 4. Сколько автомобилей должна проверить автоинспекция?

Решение. Второй и третьей цифрами номера могут быть любые две из следующих: 2, 3, 5, 6, 7, 8, 9, 0. Выбрав любую пару цифр, автоинспектор получит номер какого-либо автомобиля. Например, пара 5, 7 дает номер 1574. Эти же цифры, но в другом порядке дают номер 1754. Следовательно, нужно перебрать столько номеров, сколько будет всевозможных комбинаций из восьми перечисленных цифр по две с учетом их порядка. Такие комбинации называют размещениями. В данном случае мы ищем число размещений из восьми цифр по две.

Определение. Размещением из п элементов по k называется всякая перестановка из k элементов, выбранных каким-либо способом из данных п.

Число всех размещений из п элементов по k обозначается А_п.

Теорема 3. Число всех размещений из п элементов по k вычисляется по формуле

                                                     (5)

Эта теорема доказывается так же, как и теорема 2. Каждое размещение можно получить с помощью k действий. Первое действие — выбор первого элемента — осуществляется п способами, второе действие — выбор второго элемента — (п - 1) способами, и т.д., наконец, последнее действие — выбор k-того элемента — (п - k + 1) способами. По правилу умножения число всех размещений будет п(п - 1) • • • (п - k + 1), что и требовалось доказать.

Вернемся к примеру 2. Согласно формуле (5) автоинспекция должна проверить  = 8 • 7 = 56 автомобилей.

УПРАЖНЕНИЯ

12. На трех карточках написаны буквы Р, А, К. Сколько различных слов можно составить, если словом считается любой набор из двух букв? Запишите эти слова.

13. В домоуправлении трудится 6 человек. Поступило распоряжение о премировании трех сотрудников (различными суммами). Сколькими способами можно это сделать?

14. На железнодорожной ветке Дрюково—Стуково имеется 10 станций. В течение дня с каждой станции на каждую другую выехало в точности по одному пассажиру. Сколько билетов было куплено в этот день?

15. Сколькими способами можно выбрать из семи разных книг какие-либо четыре и подарить их четырем милиционерам, занявшим первые четыре призовых места на конкурсе «Настоящий мужчина города Брюкова»?

16. Студенты одной группы должны сдать 5 экзаменов в течение восемнадцати дней. Сколькими способами можно составить расписание экзаменов, если в один день разрешается сдавать не более одного экзамена?

17. В течение дня из Брюкова в Стуково отправляется 8 автобусов. Разведенные супруги гражданин N и гражданка М не хотят ехать в одном автобусе. Сколькими способами они могут отправиться в разных автобусах?

Пример 3. День Брюквы

Согласно древнему обычаю, самый главный праздник в Брюкове — День Брюквы, проводится за счет средств городского бюджета и празднуется столько дней, сколько депутатов проголосует за то, чтобы праздник состоялся. Из десяти депутатов «за» проголосовали семь.

Каково число всех возможных вариантов голосования?

Решение. Мы должны найти число всех возможных групп из семи депутатов. Здесь порядок выбора не играет никакой роли, поэтому рассматриваемые комбинации отличаются одна от другой только составом лиц. Комбинации такого типа называются сочетаниями.

Определение. Сочетанием из п элементов по k называется всякая совокупность k элементов, выбранных каким-либо способом из данных п элементов.

Число всех сочетаний из п элементов по k обозначается . В примере 3 нужно найти .

Теорема 4. Число всех сочетаний из п элементов по k вычисляется по формуле

                                       (6)

Доказательство. Возьмем какое-нибудь сочетание из п элементов по k

Переставляя эти элементы всевозможными способами, получим k! всех размещений из п по k одного и того же состава. Таким образом, из одного сочетания получается k! размещений. Следовательно, из С_п сочетаний получится С_п • k! размещений, т.е.

Отсюда, с учетом формулы (5) получаем:

,

что и требовалось доказать.

В примере 3 было п = 10, k = 7, поэтому число всех вариантов голосования присяжных равно

УПРАЖНЕНИЯ

18. В группе 30 студентов. Сколькими способами можно выбрать 6 делегатов для переговоров с администрацией института по вопросу о свободной продаже пива в студенческом буфете?

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

20. Для участия в соревнованиях тренер отбирает 5 спортсменов из двенадцати. Сколькими способами он может составить команду?

21. На окружности выбрано 7 точек. Сколько можно построить треугольников с вершинами в этих точках?

22. На карточке спортлото 36 клеток. Играющий должен отметить 4. Каково число всех возможных вариантов?

Числа сочетаний  обладают многими важными свойствами. Некоторые из них понадобятся нам в дальнейшем. Например,

=                                                                              (7)

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

Формула (7) сокращает вычисления, например:

Заметим, что формулы (4)-(6) допускают более широкое толкование. По определению полагают 0! = 1, А_п =1, =1.

Числа  также называют биномиальными коэффициентами, с их помощью записывается так называемая формула бинома Ньютона:

(а + b)^п = аⁿ + a^n-1b + a^n-1b² + ... + аb^n-1 +bⁿ

В лекции "9 Художественная культура Древнего Египта" также много полезной информации.

Эту формулу можно доказать, например, методом математической индукции. Попробуйте сделать это самостоятельно .

ТИПОВЫЕ ЗАДАНИЯ

1. Анкета по изучению общественного мнения содержит 10 вопросов, на каждый из которых отвечающий дает один из трех ответов: «да», «нет», «не знаю». Найти число всех различных способов заполнения анкеты.

2. Одна из воюющих сторон захватила в плен 12 солдат, а вторая 14. Сколькими способами можно обменять 5 военнопленных?

3. В партии из ста деталей имеется 10 бракованных. Наудачу выбирают 4 детали. Сколькими способами можно это сделать? Сколько будет четверок, не содержащих бракованных деталей? Найдите отношение числа последних к числу первых.