Материал: Михайленко Е.В. Математика. Ч. 1. Элементы общей алгебры

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

Напомним, что факториалом числа n называют произведение первых n натуральных чисел и обозначают n! = 1 2 3 … (n – 1) n. Кроме того, полагают, что 0! = 1. Умножив и разделив нашу формулу на (n – k)!, имеем:

Ak n(n 1)(n 2)...(n k 1)(n k)!. n (n k)!

Учитывая, что (n – k)! = 1 2 3 … (n – k), после преобразования числителя окончательно получим:

Ank (n n!k)!.

Пример. Найдем количество размещений из пяти элементов по три. Решение. Используя формулу размещений без повторений имеем:

Пример. Для решения оперативной задачи необходимо назначить 4 сотрудников из 12 имеющихся. Определить количество всех возможных вариантов составления списка назначенных сотрудников.

Решение. Обратим внимание на то, что порядок следования сотрудников в составляемом списке имеет значение (например, сотрудники направляются на разные объекты или могут выполнять различные обязанности) и в списке сотрудники повторяться не могут, то данная конфигурация будет размещением без повторений. Тогда, используя формулу для нахождения количества размещений из двенадцати по четыре, получим:

Таким образом, число всех возможных вариантов составления списка назначенных сотрудников равно 11880.

96

Пример. В учебной лаборатории находится 10 столов. Сколькими способами за ними могут сесть 15 курсантов, если каждый стол рассчитан не более чем на двух человек?

Решение. Установим, что количество посадочных мест в аудитории равно 20. Затем отметим, что из этих двадцати мест будет использовано только 15 (по числу курсантов в группе). Очевидно, что каждый курсант может занять только одно место за столом, то есть каждое место будет использовано только один раз, без повторов. Теперь мы видим, что данная конфигурация является размещением без повторений из двадцати по пятнадцати, следовательно:

Значит, существует 20 274 183 401 472 000 способов посадки пятнадцати курсантов за десять столов.

Можно рассуждать иначе. Для первого курсанта существует 20 способов выбора места в аудитории. Так как одно место уже занято, то для второго курсанта способов занять место остается 19. После того, как расселись 14 курсантов, последнему пятнадцатому придется выбирать только из 6 оставшихся мест. В виду того, что способы для каждого курсанта могут последовательно состояться, то согласно правилу произведения перемножим все натуральные числа от шести до двадцати включительно и получим тот же ответ.

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

Перестановки без повторений

Частным случаем размещений без повторений являются перестановки.

Определение перестановок без повторений. Размещение из n элементов по n элементов называется перестановкой из n элементов. Различные

97

перестановки из n элементов отличаются только порядком элементов. Обозначаются перестановки знаком Pn .

Формулу перестановок из n элементов легко получить из формулы для размещений. По определению перестановок имеем:

Таким образом,

Pn n!

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

Решение. В нашей задаче мы выбираем все шесть элементов из имеющегося множества автомобилей. Порядок нахождения машин в колонне важен. Каждый автомобиль уникален, и поставить его в колонну два или более раз мы не сможем. Тогда по формуле перестановок без повторений имеем:

P6 6! 12345 6 720.

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

Решение. Данная задача содержит дополнительные ограничения порядка элементов. Разобьем представленное множество книг на 3 части согласно представленным научным разделам: математика, физика, программирование. Каждый раздел на полке должен иметь свое место. Количество способов установления порядка разделов можно определить, как число перестановок из трех элементов:

P3 3! 123 6.

Но и в каждом научном разделе книги также могут иметь свой порядок. Аналогично рассчитаем количество способов размещения книг по каждой дисциплине.

98

Учитывая все вышесказанное и используя правило умножения, получим:

P3 P5 P2 P4 6 120 2 24 34560.

Сочетания без повторений

Мы рассматривали конфигурации, в которых место элементов в выбранном подмножестве имел существенное значение. Но на практике часто порядок элементов не имеет никакого значения.

Определение сочетания без повторений. Пусть имеется множество,

состоящее из n элементов. Каждое его подмножество, содержащее k элементов, называется сочетанием из n элементов по k элементов.

Это определение имеет и другую формулировку. Сочетания из n элементов по k элементов – это все k-элементные подмножества n-элементного множества, причем различными подмножествами считаются только те, которые имеют только неодинаковый состав элементов. Подмножества, отличающиеся друг от друга только порядком следования элементов, в этом случае не считаются различными. Обозначаются сочетания символом Cnk (число сочетаний из n по k).

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

содержащие k элементов, их число равно Cnk . Тогда из каждого указанного подмножества (содержащего k элементов) перестановкой его элементов можно получить все упорядоченные подмножества, которых будет ровно в k! раз больше, так как каждое k-элементное множество можно упорядочить k! способами. Значит

Ank k!Cnk Pk Cnk .

Следовательно,

99

Таким образом, количество сочетаний из n по k определяется формулой

Пример. Необходимо выбрать для букета семь из пятнадцати имеющихся у продавца алых роз. Сколькими способами это можно осуществить?

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

Таким образом, количество способов данного выбора равна 6435.

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

Решение. Для решения задачи определимся, что производится одновременный выбор элементов из двух множеств. Из девяти юношей мы выбираем пять человек, а из семи девушек – три человека. По условию задачи все выбираемые элементы не могут повторяться, а их порядок в выбранных подмножествах неважен. По формуле количества сочетаний без повторений получим: