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

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

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

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

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

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

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

* Более подробно о перестановках будет сказано в гл. VIII «Математические структуры».

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

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

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

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

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

Рп = N!. (4)

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

УПРАЖНЕНИЯ

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

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

9. Проверьте равенство P6 = 6Р5.

10. Что больше: P7 или 27?

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 вычисляется по формуле

Эта теорема доказывается так же, как и теорема 2. Каж­дое размещение можно получить с помощью K действий. Первое действие — выбор первого элемента — осуществ­ляется П способами, второе действие — выбор второго элемента — (N – 1) способами, и т. д., наконец, последнее действие — выбор K-того элемента — (п – K + 1) способа­ми. По правилу умножения число всех размещений будет П(п – 1) • • • (N – 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 вычисляется по формуле

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

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

.

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

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

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

УПРАЖНЕНИЯ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

< Предыдущая		Следующая >