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

Пусть S – множество, содержащее п неразличимых объектов. Тогда количество различных перестановок, образованных выбором k элементов с повторением, равно п^k.

Пример 1. Лототрон содержит 500 шаров с номерами. Из него выбирают шар, номер которого записывают. Шар возвращают в лототрон и процедура повторяется. Так продолжается до тех пор, пока не наберется комбинация из пяти номеров. Подсчитаем количество возможных комбинаций чисел. Для каждого из пяти чисел имеется 500 способов выбора. Следовательно, число различных комбинаций составляет 500⁵.

Пример 2. Сколько существует индивидуальных номеров карточек социального страхования?

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

Количество различных сочетаний из k объектов по п с повторением равно

Пример 3. Если в булочной продается 10 различных видов пончиков, то сколькими способами можно выбрать дюжину пончиков? Поскольку 12 пончиков выбираются из 10 различных типов с повторением, то имеются

различных способов выбрать дюжину пончиков.

Количество различных сочетаний из k объектов по п с повторением, когда необходимо выбрать хотя бы по одному объекту каждого типа, равно

Пример 4. Если в булочной продается 10 различных видов пончиков, то сколькими способами можно выбрать две дюжины пончиков, если необходимо выбрать хотя бы по одному пончику каждого вида? Если бы не было последнего ограничения, то для выбора двух дюжин пончиков из 10различных видов существовало бы различных способов. Однако, учитывая ограничение, можно выбрать только 24-10=14 пончиков из 10 различных видов, что дает различных вариантов выбора.

Если среди п элементов п₁ элементов одного вида, п₁ элементов другого вида и т.д.. то число перестановок с повторениями определяется формулой

, где п₁+ п₂+…+п_k=п

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