Схема выбора с возвращением

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

(1.4)

Если при выборке k элементов из п элементов возвращаются обратно без последующего упорядочивания (таким образом, одни и те же элементы могут выниматься по нескольку раз, т.е. повторяться), то полученные выборки есть сочетания с повторениями. Число всех сочетаний с повторениями из п элементов по k обозначается символом и вычисляется по формуле

(1.5)

Пусть в множестве из п элементов есть k различных типов элементов, при этом 1-й тип элементов повторяется п₁ раз, 2-й – п₂ раз,..., k -й – п_k раз, причём п₁ + п₂ +… + п_k = п. Тогда перестановки элементов данного множества представляют собой перестановки с повторениями.

Число перестановок с повторениями (иногда говорят о числе разбиений множества) из п элементов обозначается символом и вычисляется по формуле

(1.6)

Итоговая сводка формул приведена в следующей таблице.

Таблица 1 – Сводка формул для количества различных видов выборок

Выборка	Порядок важен	Порядок не важен
	часть элементов	все элементы
	Размещения	Перестановки	Сочетания
Без повторений
С повторениями		(п1 + п2 +… + пk = п)

Примечание. Чтобы найти по таблице нужную формулу для количества комбинаций, нужно ответить на следующие вопросы: «Допускаются ли повторения элементов при получении комбинации?», «Важен ли порядок элементов в полученной комбинации» и если порядок важен, то «В комбинации все элементы исходного множества или только их часть?»

Примечание 2. Формула Стирлинга для приближённого вычисления факториала при больших n

Пример. Сколько различных трёхзначных чисел можно составить из цифр 0, 2, 3, 5, 7 если:

а) цифры не повторяются; б) цифры могут повторяться?

Решение. а) Первую цифру можно выбрать четырьмя способами (числа вида 025 = 25, 073 = 73, … не считаем трёхзначными). Выбрав первую цифру (например, цифру 5), вторую цифру можно также выбрать четырьмя способами (второй цифрой может быть любая из оставшихся 0, 2, 3, 7). Третью цифру, очевидно, можно выбрать тремя способами. Следовательно, согласно правилу умножения имеется 4 ∙ 4 ∙ 3 = 48 способов расстановки цифр, т.е. искомых трёхзначных чисел будет 48 (вот некоторые из них: 500,237, 530,702,...).

б) Понятно, что если цифры могут повторяться, то трёхзначные числа можно составить
4 ∙ 5 ∙ 5 = 100 способами (вот некоторые из них: 222, 200,332,...).

Пример 2. В потоке 79 студентов. В лекционной аудитории 90 мест. Сколько существует вариантов размещений студентов на лекции.

Решение. Так как на лекции могут присутствовать не все студенты из потока, то обозначим количество присутствующих через n. Очевидно, что n – целое от 0 до 79. Количество способов выбрать n студентов из 79 равно количеству сочетаний из 79 человек по n (т.к. порядок присутствующих не важен, каждый студент может присутствовать только один раз на одной лекции и берётся только часть студентов). Присутствующие n студентов размещаются в аудитории (порядок важен, без повторений и заняты только часть мест аудитории), поэтому количество способов равно . Так как присутствие и расположение в аудитории определяются независимо, то по теореме умножения количество способов, при которых в аудитории находится n студентов равно . Так как количество присутствующих в аудитории определяется однозначно (например, не может быть сразу и ровно56 и ровно 72 студента), то по теореме сложения искомое количество вариантов равно . Значение данного выражения можно легко найти, используя компьютер: . Этот пример является хорошей иллюстрацией того, насколько быстро растёт количество комбинаций даже при не очень больших исходных множествах. Заметим, что можно дополнительно потребовать, чтобы количество студентов было не меньше четверти общей численности, тогда получим . А при отсутствии менее от общего количества студентов (т.е. 10 человек) получаем , что составляет 99,28% от общего количества способов!