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

Мы уже рассмотрели перестановки в предыдущей статье. Теперь перейдем к следующей сложной теме – размещениям.

И снова название говорит само за себя.

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

Здесь порядок не имеет значение.

Рассмотрим тот же пример с канцелярией. Пусть у нас есть 3 предмета: ручка, ластик, карандаш. Нам необходимо найти, как можно выбрать 2 предмета из 3-х. В этом случае k=2, а n=3. Мы можем выбрать их следующим образом:

ручка + ластик

Возникает вопрос: все ли это наборы значений? Ответ прост, не все: у нас есть ещё следующие варианты:

ручка + карандаш

ластик + карандаш

Возникает следующий вопрос: а разве нельзя взять набор: ластик + ручка? 

Конечно, можно, даже нужно, у нас же порядок не имеет значения, то есть ручка + ластик и ластик + ручка – 2 разных набора. Тогда у нас есть еще варианты:

ластик + ручка

карандаш + ручка

карандаш + ластик

Итого: всего из трех предметов мы можем выбрать 2 предмета шестью  способами.

Вроде, не сложно, пока всё понятно.

Для создания трехзначного пароля используют символы из алфавита {a, b, n, k, l}. Сколько всего паролей без повторений символов можно составить? 

Эта задача легко решается с помощью правила произведения, которое мы уже рассмотрели. Для наглядности изобразим 3 позиции для нашего пароля, на которые мы будем выбирать буквы из набора {a, b, n, k, l}.

На первое место можно поставить все 5 букв, на второе уже остаётся 4 буквы, так как одну уже использовали, тогда на третье место мы можем поставить уже 3 буквы, получаем:

Думаю, вы заметили сходство с перестановками, но отличие здесь в том, что на последнем месте стоит 3, а не 1, как в случае перестановок, и количество позиций не совпадает с набором. Итак, мы получаем, что количество размещений равно:

Построим полное дерево всех комбинаций, которые нам бы пришлось перебирать:

 Их число можно вычислить по выведенной формуле:

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

Вроде, и сейчас не сложно и понятно.

Возьмем нашу задачу с канцелярией, у нас также есть: ручка, ластик, карандаш. Но теперь у нас предметы могут повторяться, нам опять же необходимо найти, как можно выбрать 2 предмета из 3х. Посмотрим на первую комбинацию:

ручка + ручка

Возник вопрос: а разве можно взять ручку два раза?

Да, можно! У нас же в условии сказано, что предметы могут повторяться, а, значит, и может быть такая комбинация. Мы можем использовать один и тот же предмет несколько раз. Тогда распишем все остальные варианты:

ручка + ластик

ручка + карандаш

ластик + ручка

ластик + ластик

ластик + карандаш

карандаш + ручка

карандаш + ластик

карандаш + карандаш

Итого: мы получили 9 комбинаций.

Общее количество размещений с повторениями можно определить по формуле:

Для создания трехзначного пароля используются символы алфавита {1, 3, 5, 7}. Сколько всего паролей можно составить?

Решение: Здесь k=3, так как нам нужно выбрать на 3 позиции символы, n = 4, так как набор алфавита из четырех цифр. Значит, число размещений с повторениями равно всевозможному числу последовательностей длины 3 составленных из 4-символьного алфавита:

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