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

Размещение с повторениями из n элементов по m(m × n) элементов может содержать любой элемент сколько угодно раз от 1 до m включительно, или не содержать его совсем, то есть каждое размещение с повторениями из n элементов по m элементов может состоять не только из различных элементов, но из m каких угодно и как угодно повторяющихся элементов.

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

Число размещений с повторениями из n элементов по m элементов будем обозначать символом (c повт.)

Можно доказать, что оно равно n^m.

(1.3)

Пример 1.2. Изменим условиепримера 1.1. Правление коммерческого банка выбирает из 10 кандидатов трех человек на три различные должности, Предположим, что один и тот же отобранный из 10 претендентов кандидат, может занять не только одну, но и 2, и даже все 3 различные вакантные должности. Сколько в этом случае возможно комбинаций замещения трех вакантных должностей?

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

По условию задачи n = 10, m = 3.

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

_{(с повт.)} = 10³ = 1000.

Ответ. Можно составить 1000 комбинаций замещения 3 различных вакантных должностей.

Сочетания

Сочетаниями из n элементов по m в каждом называются такие соединения, каждое из которых содержит m элементов, взятых из числа данных n элементов, и которые отличаются друг от друга по крайней мере одним элементом.

Число сочетаний из n элементов по m в каждом обозначается символом и вычисляется так:

где ,

(1.4)

или

где .

(1.5)

Свойства сочетаний:

Пример 1.3. Правление коммерческого банка выбирает из 10 кандидатов трех человек на одинаковые должности (все 10 кандидатов имеют равные шансы). Сколько всевозможных групп по три человека можно составить из 10 кандидатов?

Решение. Состав различных групп должен отличаться, по крайней мере, хотя бы одним кандидатом и порядок выбора кандидата не имеет значения, следовательно, этот вид соединений представляет собой сочетания. По условию задачи n = 10? M = 3. Подставив данные в формулу (1.4.2), получаем

= 10!/3!7! = 120

Ответ. Можно составить 120 групп из 10 человек по 3.

Замечание. Надо уметь отличать сочетания от размещений. Если, например, в группе 25 студентов, и 10 человек из них вышли из аудитории на перерыв. Они стоят вместе и беседуют. Тогдапорядок, в котором они стоят - несущественен. Число всех возможных групп из 25 человек по 10 в этом случае - сочетания. Если же студенты отправились на перерыве в буфет, или в кассу за стипендией, то тогда существенно, в каком порядкеонивстали, то есть кто из них первый, второй и т.д. В этой ситуации при подсчете возможных групп из 25 человек по 10 необходимо составлять размещения.