Размещения без повторений
Рассмотрим задачу: Сколько разных 5-разрядных чисел можно записать с помощью десяти цифр при условии, что в числах не используются одинаковые цифры?
IIеренумеруем разряды:
В первый разряд можно поставить одну из 10 цифр (0,1,2, 3,4, 5, 6, 7, 8, 9). Независимо от того, какая цифра помещена в первый разряд, во втором можно поставить только одну из 9 цифр, в третий - одну из 8 цифр и т. д. Всего существует 10 · 9 · 8 · 7 · 6 = 30240 различных пятиразрядных чисел, в каждом из которых нет двух одинаковых цифр.
В общем случае, если имеется k позиций и n разных предметов, причем каждый представлен в единственном экземпляре, то количество разных расстановок:
(3)
В формуле (3) s! означает факториал числа s, т. е. произведение всех чисел от 1 до s. Таким образом, s! = 1 · 2 · 3 · ...s.
Пример. Из группы в 25 человек требуется выбрать старосту, заместителя старосты и профорга. Сколько вариантов выбора руководящего состава группы? Старосту выбрать можно одним из 25 способов. Поскольку выбранный староста не может быть своим заместителем, то для выбора заместителя старосты остается 24 варианта. Профорга выбирают одним из 23 способов. Всего вариантов: 25 · 24 · 23 = 25!/22! - 13800.
Упражнения
1. Из коллектива работников в 25 человек нужно выбрать председателя, заместителя, бухгалтера и казначея. Каким количеством способов это можно сделать? (25 · 24 · 23 · 22 = 25!/(25 - 4)! = 303600)
2. В парламент нового независимого государства нужно представить для рассмотрения варианты флагов (для определенности - три горизонтальных полосы). Сколько вариантов флагов можно представить, если каждый флаг должен содержать три разных цвета, а количество цветов имеющегося материала, из которого делаются флаги, равно 12? (12!/9! = 1320)
3. На дискотеку пришло 12 девушек и 15 юношей. Объявлен "белый" танец. Все девушки выбрали для танцев юношей (и никто из них не отказался). Сколько могло образоваться танцующих пар? (15!/(15 - 12)!)
