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

Таким образом, количество комбинаций выбора юношей равно 126, а девушек – 35. Так как оба выбора осуществляются одновременно, то необходимо использовать правила произведения:

C95 C73 126 35 4760.

Значит, количество вариантов назначения в наряд курсантов равно 4760. Пример. Сколько существует способов расстановки двадцати

полицейских для охраны трех объектов, если для выполнения задания на каждый из этих объектов требуется пять сотрудников?

Решение. Задачу разделим на три этапа, по количеству охраняемых объектов. На первый объект требуется пять полицейских, следовательно количество вариантов расстановки сотрудников будет:

На второй объект выберем следующие пять полицейских из пятнадцати оставшихся:

И, наконец, на третий объект выберем еще пять полицейских из десяти:

Так как все вышеперечисленные выборы осуществляются одновременно, то используя правило умножения получим ответ:

C205 C155 C105 15505 3003 252 11 733501780.

Таким образом, для охраны трех объектов можно выделить полицейских

11 733 501 780 способами.

6.3.Комбинаторные конфигурации с повторениями

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

объединенных по какому-либо определяющему признаку. Такие конфигурации

101

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

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

Определение. Пусть имеется множество, содержащее n элементов. Упорядоченный набор из k элементов, среди которых могут быть одинаковые элементы, называется размещением с повторениями из n элементов по k элементов.

Можно привести другую формулировку определения размещений с повторениями.

Размещение с повторениями из n элементов по k – это все k-элементные множества, в которых каждый элемент исходного множества может повторяться, отличающиеся составом элементов или порядком их следования.

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

Количество размещений с повторениями обозначаются символом Ank (число размещений с повторениями из n по k). Из правила произведения можно получить формулу для подсчета количества размещений с повторениями:

Ank nk .

Пример. Сейф имеет сложный цифровой замок, состоящий из 10 дисков. На каждом диске можно выставить цифру от «0» до «9» или латинскую букву от «A» до «F». Сколькими различными наборами знаков может быть представлен код замка.

Решение. В настоящей задаче представлено множество, состоящее из 16

элементов: «0», «1», «2», «3», «4», «5», «6», «7», «8», «9», «A», «B», «C», «D»,.«E»,.«F». Из заданного множества необходимо выбрать 10 элементов, причем составленные конфигурации являются упорядоченными, а каждый элемент в наборе может повторяться не более 10 раз. Например, набор

«А», «А», «А», «7», «7», «7», «7», «7», «7», «7»

102

содержит три буквы «А» и семь цифр «7». Тогда, используя формулу числа размещений с повторениями из 16 по 10, получим:

A1610 1610 1099511627776.

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

В конфигурации размещение с повторением количество выборок k может быть больше, чем количество элементов n исследуемого множества.

Пример. Имеется 23 красных, 42 синих и 19 желтых шаров. Шары отличаются только цветом. Случайным образом отобраны 8 шаров и расставлены в ряд. Сколькими способами может быть составлен такой ряд?

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

A38 38 6561.

Следовательно, количество способов составления упорядоченного ряда из 8 шаров равно 6 561.

Пример. Сколькими способами можно разместить 7 служебных автомобилей в 5 секторах охраняемой территории при условии, что в каждом секторе осталось достаточно свободных парковочных мест для размещения всех автомобилей.

Решение. Эту задачу можно рассмотреть следующим образом. Будем исходить из того, что для размещения каждого автомобиля имеется множество из пяти повторяемых свободных парковочных мест, по одному на каждом секторе. Мы выбираем сектор! Номер места в каждом секторе не важен, зато упорядочены автомобили, то есть имеет значение, в каком секторе разместится

103

тот или иной автомобиль. Следовательно, применяя формулу числа размещений с повторениями из пяти элементов по семь, получим:

A57 57 78125.

Значит, количество способов для размещения 7 служебных автомобилей в 5 секторах охраняемой территории равно 78 125.

Перестановки с повторениями

Определение. Пусть дано множество, состоящее из n элементов. Упорядоченный набор k элементов этого множества такой, что 1-й элемент взят k1 раз, 2-й элемент - k2 раза, …, n-й элемент - kn раз (k1 + k2 + … +kn = k) называется перестановкой с повторениями длины k из n элементов.

Приведем другую формулировку определения размещений с повторениями. Перестановкой с повторениями из n элементов по k называется всякое k-элементное множество, в котором каждый i-й элемент заданного множества повторяется ki раз, отличающееся составом элементов или порядком их следования.

Количество перестановок с повторениями длины k из n разных элементов, взятых соответственно по k1, k2, …, kn раз каждый, обозначается P(k1, k2, …, kn). Формула для числа перестановок с повторениями получается непосредственно из правила умножения:

P(k1,k2,...,kn ) k1! k2!k! kn!.

Пример. Для посадки декоративных деревьев в парке Краснодарского университета МВД подготовлены 20 лунок. Сколькими способами можно разместить в них 8 лип, 5 кленов и 7 катальп, если считать деревья одного сорта одинаковыми?

Решение. Можно считать, что мы имеем множество сортов декоративных деревьев, состоящее из n = 3 элементов: «липа», «клен» и «катальпа». Каждый элемент повторяется: количество лип k1 = 8, кленов k2 = 5, катальп k3 = 7. Всего k = 20 деревьев. Тогда, используя формулу числа перестановок с повторениями, получим:

104

Сократив значения факториалов, получим, что посадку деревьев можно сделать 99 768 240 способами, считая деревья одного сорта одинаковыми.

Если бы в условии задачи количество лунок было бы больше, чем количество саженцев, тогда после посадки остались бы пустые лунки и следовало бы ввести еще один сорт деревьев – «пусто» и решать задачу уже с множеством из четырех повторяющихся элементов.

Сочетания с повторениями

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

Можно привести другую формулировку определения размещений с повторениями.

Сочетание с повторениями из n элементов по k – это все k-элементные множества, в которых каждый элемент может повторяться, отличающиеся только составом элементов.

Количество сочетаний с повторениями обозначаются Сnk (число сочетаний с повторениями из n по k). Формула для подсчета количества сочетаний с повторениями выглядит следующим образом:

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

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

105