08. Перестановки, размещения, , сочетания

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

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

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

Пусть дано множество из N элементов. Занумеруем их от 1 до N.

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

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

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

Первый элемент можно выбрать N Различными способами; второй выбирается из оставшихся N – 1 элементов, поэтому число всех способов выполнения второго действия будет N – 1. Далее останется N – 2 элемента, их можно разместить N – 2 способами. И т. д. Последнее действие можно выполнить одним способом. По правилу умножения число всех способов выполнения действий, т. е. число перестановок, равно (так обозначается функция факториал, т. е. произведение всех членов натурального ряда до N Включительно). ■

Число перестановок обозначается РN:

(4)

В случае с новобранцами (N = 5) РN = 5! = 120.

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

Решение. Вторую и третью цифры надо выбирать из восьми, а именно из 0, 2, 3, 5, 6, 7, 8, 9. Если выбрать вторую цифру восемью способами, то для третьей цифры останется 7 вариантов. Отсюда 8×7 = 56 способов.

Нужно перебрать из восьми цифр по две с учетом их порядка, поскольку 1674 и 1764 – разные номера. Такие комбинации называют размещениями.

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

Число размещений обозначается .

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

(5)

(в этой формуле K сомножителей).

Доказательство. Аналогично теореме 2. Каждое размещение можно получить с помощью K действий. Первое действие можно выполнить N способами, второе – N- 1 способами и т. д., K действие – (N – K + 1) способами. По правилу умножения , что и требовалось доказать. ■

Для рассмотренного выше примера .

Пример. Из 10 депутатов поселкового совета 7 проголосовали «за». Каково число всех возможных вариантов голосования?

Здесь порядок выбора не играет роли, поэтому комбинации отличаются только составом лиц. Такие комбинации называются сочетаниями.

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

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

(6)

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

(A, B, C, … , F) - здесь K букв.

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

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

В последнем примере = 10, = 7,

Другая формула для числа сочетаний имеет вид:

Теорема 5.Свойство :

(7)

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

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

По определению 0! = 1, .

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

Эту формулу можно доказать методом математической индукции.

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